IntersectionOfTwoLinkedLists2 [source code]

public class IntersectionOfTwoLinkedLists2 {
static
/******************************************************************************/
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        int lenA = length(headA), lenB = length(headB);
        while (lenA > lenB) {
            lenA--;
            headA = headA.next;
        }
        while (lenB > lenA) {
            lenB--;
            headB = headB.next;
        }
        while (headA != headB) {
            headA = headA.next;
            headB = headB.next;
        }
        return headA;
    }

    public int length(ListNode head) {
        int res = 0;
        while (head != null) {
            res++;
            head = head.next;
        }
        return res;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        IntersectionOfTwoLinkedLists2.Solution tester = new IntersectionOfTwoLinkedLists2.Solution();
        int[][] inputs = {
            {1,2,3,4}, {9,8}, {5, 6, 7},
            {1}, {}, {},
            {1,3,5,7,9,11,13,15,17,19,21}, {2}, {},
            {}, {}, {1,2,3,4,5,6,7,8,9,10,11,12,13},
        };
        for (int i = 0; i < inputs.length / 3; i++) {
            System.out.println(Printer.seperator());
            ListNode h1 = ListNode.buildListNode(inputs[3 * i]);
            ListNode h2 = ListNode.buildListNode(inputs[1 + 3 * i]);
            ListNode h3 = ListNode.buildListNode(inputs[2 + 3 * i]);
            ListNode headA = ListNode.append(h1, h3);
            ListNode headB = ListNode.append(h1, h3);
            Printer.openColor("red");
            System.out.print(ListNode.serialize (headA) + " AND " + ListNode.serialize (headB));
            Printer.closeColor();
            System.out.println(" -> " + ListNode.serialize (tester.getIntersectionNode(headA, headB)));
            Printer.openColor("green");
            System.out.println(ListNode.serialize (headA) + " AND " + ListNode.serialize (headB));
            Printer.closeColor();
        }
    }
}

这个思路是在 discussion 里面看到的一个思路, 整体的想法很简单. 如果直接从两个 head 开始扫, 找不到 intersection 的原因是因为两个 list 可能长度不一样; 所以我们人为的进行一下补偿就行了;

还是注意 loop header 的写法: header condition is yes-condition, and what you WANT is the terminating condition;

最后的速度是2(37);

这个是 discussion 最优解:

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {  
    //boundary check  
    if(headA == null || headB == null) return null;  

    ListNode a = headA;  
    ListNode b = headB;  

    //if a & b have different len, then we will stop the loop after second iteration  
    while( a != b){  
        //for the end of first iteration, we just reset the pointer to the head of another linkedlist  
        a = a == null? headB : a.next;  
        b = b == null? headA : b.next;      
    }  

    return a;  
}

这个比普通的补偿做法的有点在于, 不需要explicitly 的去计算这个差值: 他这里第一个 iteration 跑完之后, 两个指针的位置就自动对齐了;
另外这个算法看起来有点像是主动构造 cycle 的做法(因为 LinkedList 里面 cycle 也跟 reverse 一样是一个常用的也好处理的技巧), 不过好像并不能完全这样说, 因为他这里最后只可能跑两圈.
他这里的这个思路可以是这样: 还是两个指针赛跑思路, 但是我们想要他们共同起跑. 两个 list 长度不一样的情形, 可以理解为一个指针需要跑的距离比另一个指针需要跑的距离要长: 那么我们就让跑的快(短)的那个, 跑完了直接再去跑长的; 跑的长的, 跑完了直接去快车道, 这样长度差值就补偿掉了;

真正想到这个算法还是挺难的, 我个人看法这个就是一个值得称赞的小 trick, 不过真正面试的时候不用执迷于这种技巧; 这个算法其实并没有提高速度;

这个是 discussion 上面一个稍微有点奇葩的解法:

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {  
    ListNode *tmp = headB;  
    int amoutB = 0,lengthB=0;  

    //calculate the amount of values in listB and get the length of listB  
    while (tmp!=NULL)  
    {  
        amoutB += tmp->val;  
        lengthB ++;  
        tmp = tmp->next;  
    }  

    //add 1 value to all nodes in listA  
    tmp = headA;  
    while (tmp!=NULL)  
    {  
        tmp->val++;  
        tmp = tmp->next;  
    }  

    //re-calculate the amount of values in listB again  
    tmp = headB;  
    int newamoutB = 0;  
    while (tmp!=NULL)  
    {  
        newamoutB += tmp->val;  
        tmp = tmp->next;  
    }  
    tmp = headA;  

    //subtract 1 from all the nodes in listA  
    while (tmp!=NULL)  
    {  
        tmp->val--;  
        tmp = tmp->next;  
    }  

    //if two amounts are the same, there is no node intersecting  
    if(newamoutB==amoutB)  
       return NULL;  
    //the difference of two amounts means the number of intersecting nodes,   
    //we can get the first one by comparing it with number of nodes in listB  
    else  
    {  
        tmp = headB;  
        for(int i=0; i<lengthB-(newamoutB-amoutB);i++)  
            tmp = tmp->next;  
        return tmp;  
    }  
}

整体思路就是如果两个 list 有共享的 node, 那么我们修改其中一个 list 里面所有的 val, 另外一个 list 所有的 val 也会改变. 用 sum 来记录这个改变(来达到O(1)空间), 然后最后这个差值就是number of nodes shared.
不过底下还是有人认为这个算法有问题, 因为这个算是改变了;
另外这个算法有一个问题, 如果这里的 intersection 不是一直持续到两个 list 的底部, 也就是说 intersection 一段之后有分叉, 那么这个算法就不对了; 我自己的 reverse 的算法好像也 handle 不了这种情况; //分个屁的叉! 根本不可能分叉! 一个 node 只可能有一个 child, 一旦汇合就不可能分叉. 不过这个问题想到一次也好, 不然面试的时候碰到了也是自己蠢自己;

Problem Description

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
begin to intersect at node c1.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.
  Credits:
  Special thanks to @stellari for adding this problem and creating all test cases.

Difficulty:Easy
Total Accepted:134.4K
Total Submissions:440.5K
Contributor: LeetCode
Companies
amazon microsoft bloomberg airbnb
Related Topics
linked list
Similar Questions
Minimum Index Sum of Two Lists