@TOC

一、移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

public ListNode removeElements(ListNode head, int val) {     
        while(head != null && head.val == val) {
            head = head.next;
        }
        if(head == null) {
            return null;
        }
        ListNode fast = head.next;
        ListNode slow = head;
        while(fast != null) {
            if(fast.val == val) {
                slow.next = fast.next;
                fast = fast.next;
            }else {
                fast = fast.next;
                slow = slow.next;
            }
        }
        return head;
    }

二、链表分割

现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        if (pHead == null) {
            return null;
        }
        if (pHead.next == null) {
            return pHead;
        }
        ListNode p1 = null;
        ListNode p11 = null;
        ListNode p2 = null;
        ListNode p22 = null;
        while (pHead != null) {
            if (pHead.val < x) {
                if (p1 == null) {
                    p1 = pHead;
                    p11 = pHead;
                } else {
                    p11.next = pHead;
                    p11 = p11.next;
                }
            } else {
                if (p2 == null) {
                    p2 = pHead;
                    p22 = pHead;
                } else {
                    p22.next = pHead;
                    p22 = p22.next;
                }
            }
            pHead = pHead.next;
        }
        if (p1 == null) {
            return p2;
        }
        if (p2 != null) {
            p22.next = null;
        }

        p11.next = p2;

        return p1;
    }
}

三、相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) {
            return null;
        }
        ListNode p1 = headA;
        ListNode p11 = p1;
        ListNode p2 = headB;
        ListNode p22 = p2;
        int len1 = 0;
        int len2 = 0;
        while(p11 != null) {
            p11 = p11.next;
            len1++;
        }
        while(p22 != null) {
            p22 = p22.next;
            len2++;
        }
        if(len1 < len2) {
            p1 = headB;
            p2 = headA;
        }
        int len = Math.abs(len1 - len2);
        while(len > 0) {
            p1 = p1.next;
            len--;
        }
        while(p1 != null && p2 != null) {
            if(p1 == p2) {
                return p1;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        return null;
    }