2017-06-08 17:46:20 +0000   |     algorithm leetcode linked list   |   Viewed times   |    

题目

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.

HashSet记录listA的所有节点

代码

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) { return null; }
        Set<ListNode> memo = new HashSet<>();
        ListNode cur = headA;
        while (cur != null) {
            memo.add(cur);
            cur = cur.next;
        }
        cur = headB;
        while (cur != null) {
            if (memo.contains(cur)) { return cur; }
            cur = cur.next;
        }
        return null;
    }
}

结果

intersection-of-two-linked-list-1

计算listAlistB的长度

比如listA长度为2listB长度为3。计算出长度差之后,让curB先跑到b2位置,和a1站在同一起跑线再出发。

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

代码

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) { return null; }
        int sizeA = size(headA);
        int sizeB = size(headB);
        ListNode curA = headA, curB = headB;
        // curA,curB归同一起跑线
        while (sizeA > sizeB) {
            curA = curA.next;
            sizeA--;
        }
        while (sizeB > sizeA) {
            curB = curB.next;
            sizeB--;
        }
        while (curA != curB && curA != null) {
            curA = curA.next;
            curB = curB.next;
        }
        return (curA == null)? null : curA;
    }
    public int size(ListNode list) {
        ListNode cur = list;
        int count = 0;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }
}

结果

intersection-of-two-linked-list-3

有个小诀窍,可以不计算长度

listA先跑到c3结尾处,跳转到listB的开头b1接着跑。listB后跑到c3结尾处,跳转到listA的开头a1接着跑。如果listAlistB相交,则会在第二圈同时到达c1。如果不想交,会同时跑到null

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

这里面的数学本质就是:

两个指针curAcurB都跑了lengthA + lengthB

代码

public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            if (headA == null || headB == null) { return null; }
            ListNode curA = headA, curB = headB;
            while (curA != curB) { // will stop after seconde iteration if no intersection exists
                curA = (curA == null)? headB : curA.next;
                curB = (curB == null)? headA : curB.next;
            }
            return curA;
        }
}

结果

intersection-of-two-linked-list-4

WalkerRunner的追逐算法

因为已经有了Linked List Cycle Two这个问题的最后一种天才的RunnerWalker的解法,我们可以在 时间复杂度,以及 空间复杂度的情况下,轻松找到Cycle开始的那个节点。所以只需要把listA或者listB其中一个首尾相接成一个cycle,问题就转变成Linked List Cycle Two问题。

最后找到拼接的头节点之后,再把造出来的cycle复原即可。

WalkerRunner追逐算法细节如下

利用walkerrunner指针,walker每轮前进一步,runner每轮前进两步。当他们相遇的时候,说明有cycle存在。这时候记下walker一共走了k步,runner就走了2k步。然后假设

这时候我们就能得到两个等式,

2k - k = nr (1式)(runner在遇到walker之前,已经绕着cycle跑了n圈了)

k = s + m (2式)(就是walker从起始点跑到和runner相遇的地方的距离,可以肯定walker没有跑完一圈)

上面的两个等式(1)(2)能推出下面这个等式(3)

s = nr - m (3式)

这个等式就是说:一个指针cur从list起始点出发,另一个指针cycleCurrunnerwalker相遇点出发,两者每轮都前进一步,最后一定在cycle的首个节点相遇。

因为假设n=1的情况,s=r-m,就是说cycleCur只要继续跑完这一圈,回到cycle首节点,cur也正好到cycle首节点。如果n=2,就是cycleCur整整多跑一圈,但curcycleCur还是在cycle首节点相遇。事实上无论n=3,4,5,6,...curcycleCur总是在cycle首节点相遇,区别只是cycleCur多跑几圈而已。

代码

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) { return null; }
        ListNode end = headA;
        while (end != null && end.next != null) { // cur stop at the last node
            end = end.next;
        }
        end.next = headA; // make a circle
        ListNode walker = headB, runner = headB;
        while (runner != null && runner.next != null) {
            walker = walker.next;
            runner = runner.next.next;
            if (runner == walker) { // find circle
                ListNode anotherWalker = headB;
                while (anotherWalker != walker) { // BLACK MAGIC
                    anotherWalker = anotherWalker.next;
                    walker = walker.next;
                }
                end.next = null;
                return walker;
            }
        }
        end.next = null;
        return null;
    }
}

结果

银弹! intersection-of-two-linked-list-2