链表相交

链表相交

1. O(n) 解法

首先计算出两个链表的长度差，使最长的链表先移动到两链表相同长度之处，再同时往后移动，边移动边比较。

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
42
43
44
45
46
47
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null)
            return null;
        
        ListNode curA = headA;
        ListNode curB = headB;

        int cntA =0, cntB=0;
        while(curA != null){
            cntA++;
            curA=curA.next;
        }

        while(curB != null){
            cntB++;
            curB=curB.next;
        }

        curA = headA;
        curB = headB;

        if(cntB > cntA){
            int tempLen = cntA;
            cntA = cntB;
            cntB = tempLen;

            ListNode temp = curA;
            curA = curB;
            curB = temp; 
        }
        int gap = cntA -cntB;
        while(gap-- > 0){
            curA = curA.next;
        }

        while(curA!=null){
            if(curA == curB)
                return curA;

            curA = curA.next;
            curB = curB.next;
        }

        return null;
    }
}

2. 双指针解法

设 A 链表长度为 $a$ , B 链表长度为 $b$ , 二者公共后缀链表长度为 $c$。

设两个指针 curA ,curB 。

curA先遍历链表 A，再遍历链表 B 至两链表相交节点处。 遍历链表A，经过的长度为 $a$ , 遍历遍历链表 B 至两链表相交节点处，经过的长度为 $b-c$ , 则curA经过的长度为 $$a+(b-c)$$

同理，curB 先遍历链表 B，再遍历链表 A 至两链表相交节点处。经过的长度为 $$b+(a-c)$$

显然 $$a+(b-c) = b+(a-c)$$

所以，如果存在相交节点，则两指针一定会相遇。

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;

        while(curA!=curB){
            curA = curA != null ? curA.next : headB;
            curB = curB != null ? curB.next : headA;
        } 

        return curA;
    }
}