LeetCode 160 Intersection of Two Linked Lists 题解

发表于 | 阅读次数:

题目

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

　　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.

解法一

思路

　　由于两个链表在尾部可能存在相同的部分，如果将其中一条链表的尾部连到另一条链表的头部，那么就可以构造一个环。题目就转化为求环的入口结点。下面先对环的几个概念作出分析。

单链表是否存在环？

　　解答这个问题，只需要设置快慢指针即可。慢指针一次走一步，快指针一次走两步。如果存在环，那么快指针终会赶上慢指针。设想一下，假如快指针追到慢指针身后一步，那么慢指针走一步，快指针走两步后，下一次就会相遇。如果快指针落后慢指针两步或者三步，再多走一次或两次两者就会达到只差一步的情况。所以两个指针终将相遇。

求环的长度。

　　从快慢指针相遇结点开始，让一个指针每次走一步，那么下次回到这个结点所走过的路程，就是环的长度。

求存在环的单链表的环的入口结点。

　　设单链表头结点到入口结点的距离为ａ，入口结点到快慢指针相遇结点的距离为ｘ，单链表总长度为L，环长为r。当快慢指针相遇时，设慢指针走的步数是s，则快指针走的步数是2s。


s = a + x;
2s = s + nr;
a + x = nr = (n-1)r + r = (n-1)r + L - a;
a = (n-1)r + L - a - x;

　　所以，设置两个指针，起点分别是链表头结点和快慢指针相遇结点，同时前进，每次走一步。那么总会相遇在入口结点处。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null){
            return null;
        }
        ListNode temp = headA;
        while(temp.next != null){
            temp = temp.next;
        }
        temp.next = headB;
        ListNode slow = headA;
        ListNode fast = headA;
        do{
            if(fast != null && fast.next != null){
                slow = slow.next;
                fast = fast.next.next;
            }else{
                temp.next = null;
                return null;
            }
        }while(slow != fast);
        slow = headA;
        while(slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        temp.next = null;
        return slow;
    }
}

　　这个解法实际上就是求存在环的单链表的环的入口结点。

解法二

　　这两个链表有一个特点，就是相同的地方必定在尾部。但是由于两条链表长度不一定相等，如果同时遍历的话，很难让相同的结点对齐。因此，这个解法用了一个小技巧，让两个链表在按顺序从头到尾遍历的时候，能够做到尾部对齐。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null){
            return null;
        }
        ListNode p1 = headA;
        ListNode p2 = headB;
        boolean flagA = false;
        boolean flagB = false;
        while(p1 != p2){
            p1 = p1.next;
            p2 = p2.next;
            if(p1 == null){
                if(flagA == true && flagB == true){
                    return null;
                }else{
                    flagA = true;
                }
                p1 = headB;
            }
            if(p2 == null){
                p2 = headA;
                flagB = true;
            }
        }
        return p1;
    }
}

　　一开始仍然让两链表从头开始遍历，每次走一步。链表A遍历到末端回到链表B的头部，链表B遍历到末端也回到链表A的头部。这样当两个遍历指针都到达另一个链表的时候，恰好可以让尾部对齐，消除掉长度差的影响。