Linked List Problem

Algorithm

---

Idea Tips:

1. No buffer, constant memory
Using assignments to modify the orginal input, like pointer;
2. Two pointers
(Runner and walker)
Using two pointers, for locating some special position;
this idea also fit for finding a loop;
3. Recursion or iteration
These two are alternative. For recursion, it may be easy to get reversal list or element. But sometime interviewer may require to think in iteration method; 

Content：

 * 求单链表中结点的个数: getListLength 
 * 将单链表反转: reverseList（遍历），reverseListRec（递归） 
 * 查找单链表中的倒数第K个结点（k > 0）: reGetKthNode 
 * 查找单链表的中间结点: getMiddleNode 
 * 去除重复节点 (Remove Duplicate, from Sorted or unsorted) 
 * 已知两个单链表pHead1 和pHead2 各自有序，把它们合并成一个链表依然有序: mergeSortedList, mergeSortedListRec 
 * 判断一个单链表中是否有环: hasCycle & 已知一个单链表中存在环，求进入环中的第一个节点: getFirstNodeInCycle, getFirstNodeInCycleHashMap 
 * 判断两个单链表是否相交: isIntersect  &  求两个单链表相交的第一个节点: getFirstCommonNode 
 * 给出一单链表头指针pHead和一节点指针pToBeDeleted，O(1)时间复杂度删除节点pToBeDeleted: delete 

1. Reverse Method:

1. Get Head Node and Tail Node;
    Get Current Node;
    while(Current!=Tail(or null)):
        Node temp = current.next;
        Current.next = head.next;
        Head.next = current;    
        current = temp;
 2. Node newHead = null;
    Node cur = head;
    while(cur!=null):
        Node preCur = cur;
        cur = cur.next;
        preCur.next = newHead;
        newHead = preCur;
 3. reverse(head): !!!!!
        if head == null||head.next == null;
            return head;
        newHead = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;

2. Get Kth Node from rear:

TIPS: Two Pointer: runner and walker, runner go fast n steps, then go together to the end when the runner stop.

    ListNode runner = head;
    ListNode walker = head;
    int i = 0;!!!
    while(i<n):
        runner = runner.next;
        i--;
    if(runner==null)  return // check runner valid!!!
    while(runner.next!=null):
        runner = runner.next;
        walker = walker.next;

3. Get Middle of List

TIPS: Doesn't need two pointer: change the given node's val as the next node's val and change the next node of given node which point to the next.next.

        ListNode tmp = node.next;
        node.val = tmp.val;
        node.next = next.next;

4. Remove Duplicate:

4.1 for Unsorted:!!!

        ListNode pre = head;
        ListNode cur = pre.next;
        while(cur!=null):
            ListNode runner = head; // a moving pointer for comparison
            while(runner!=null):
                if(runner.val == cur.val):
                    ListNode tmp = cur.next;
                    pre.next = tmp;
                    cur = tmp;
                    break;
                else:
                    runner = runner.next;
            if(cur == runner):
                pre = cur;
                cur = cur.next;

4.2 for Sorted:

    (1) ListNode p1 = head;
        ListNode p2 = head;
        while(p2!=null):
            if(p1.val==p2.val):
                p1.next = p2.next;
            else 
                p1 = p2;
            p2 = p2.next;
    (2) ListNode fakeHead = new ListNode(0);
        fakeHead.next = head;
        ListNode pre = fakeHead;
        ListNode cur = pre.next;
        while(cur!=null):
            while(cur.next!=null&&cur.next.val==cur.val):
                cur = cur.next;
                if(pre.next == cur) // not duplicate!
                    pre = pre.next;
                else
                    pre.next = cur.next;
                cur = cur.next;
        return fakeHead.next;

5. Merge Two Sorted List:

    (1) 
        ListNode dummy = new ListNode(0);
        dummy.next = head1;
        ListNode pre = dummy;
        while(l1!=null&&l2!=null):
            if(l1.val>l2.val):
                ListNode tmp = l2.next;
                l2.next = pre.next;
                pre.next = l2;
                l2 = tmp;
            else
                l1 = l1.next;
            pre = pre.next;
        if(l2!=null)
            pre.next = l2;
        return helper.next;
    (2) 
        Node mergeHead = null;  
        if (head1.val < head2.val): 
            mergeHead = head1;  
            // 连接已解决的子问题  
            mergeHead.next = mergeSortedListRec(head1.next, head2);  
        else: 
            mergeHead = head2;  
            mergeHead.next = mergeSortedListRec(head1, head2.next);  
        return mergeHead; 

6. Check Cycle:

        ListNode walker = head;
        ListNode runner = head;
        while(runner.next!=null): 
            // please assign first, then check equivalent
            runner = runner.next.next;
            walker = walker.next;
            if(runner==walker):
                break;
        if(runner.next == null)
            return null;
        ListNode checker = head;
        while(checker!=walker):
            checker = checker.next;
            walker = walker.next;
        return checker;

7. Find Intersection:

        // check each length
        // make two equivalent
        // start new iteration to find interaction point
        ListNode dummy1 = l1;
        ListNode dummy2 = l2;
        int len1 = 0;
        int len2 = 0;
        while(dummy1!=null): 
            dummy1 = dummy1.next;
            len1++;
        while(dummy2!=null):
            dummy2 = dummy2.next;
            len2++;
        dummy1 = l1;
        dummy2 = l2;
        while(len1>len2):
            dummy1 = dummy1.next;
            len1--;
        while(len2>len1):
            dummy2 = dummy2.next;
            len2--; 
        while(dummy1!=null&&dummy2!=null):
            if(dummy1==dummy2)
                return dummy1;
            dummy1 = dummy1.next;
            dummy2 = dummy2.next;
        return null;

8. (LeetCode) Add Two Number:

    ListNode result = new ListNode(0);
    ListNode resultHead = result;
    int carry = 0;

    while(n1!=null||n2!=null||carry!=0):
        int cur = 0;
        if(n1!=null):
            cur+= n1.val;
            n1 = n1.next; // don't forget

        if(n2!=null):
            cur+= n2.val;
            n2 = n2.next; // don't forget

        cur += carry;
        carry = cur/10;
        cur %= 10;
        ListNode node = new ListNode(cur);
        result.next = node;
        result = result.next; // don't forget

    return resultHead.next;