Leetcode 02.07 链表相交（链表）

很巧妙，这就是将链表的尾端对齐后再一起遍历，这样能满足题目的要求。因为相交之后两个链表到结束的所有节点都一样了，数目也一样。

解法1 尾部对齐

时间复杂度O(M+N)
空间复杂度O(1)

/**
 * 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) {
        ListNode curA = headA;
        ListNode curB = headB;
        int Alen = 0, Blen = 0;

        if(headA == null || headB == null) return null;

        // 求两个链表的长度
        while(curA != null){
            curA = curA.next;
            Alen ++;
        }
        while(curB != null){
            curB = curB.next;
            Blen ++;
        }

        curB = headB;
        curA = headA;
        // 【长短尾部对齐】让短的那个的头结点还是其之前的头结点，长的的cur右移（长-短）
        if(Alen > Blen){ 
            for(int i = 0; i < (Alen - Blen); i++){
                curA = curA.next;
            }
        } else if(Alen < Blen){ 
            for(int i = 0; i < (Blen - Alen); i++){
                curB = curB.next;
            }
        }

        // 接下来curA 和 curB 一起向后移动寻找一样的节点
        while(curA != null){
            if(curA == curB){
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;

    }
}
       
    
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
48
49
50
51
52
53
54
55
56

解法2：太厉害了，数学归纳推导的方法

在指针 pA 移动了 a+c+b 次、指针 pB 移动了 b+c+a次之后，两个指针会同时到达两个链表相交的节点，该节点也是两个指针第一次同时指向的节点，此时返回相交的节点。
如果两个链表不相交也是一样的道理，当PA指针和PB指针同时遍历m+n后，会同时指向null。

时间复杂度O(1)
空间复杂度O(1)

/**
 * 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 PA = headA;
        ListNode PB = headB;
        // 同时遍历PA,PB，当PA到null则再指向headB，当PB到null则再指向headA
        // 遇到PA = PB 则返回该值
        // 最后同时指向null则返回null
        while(PA != PB){
            if(PA == null) {
                PA = headB;
                continue;
            }
            if(PB == null) {
                PB = headA;
                continue;
            }
            PA = PA.next;
            PB = PB.next;

        }
        if(PA == null) return null;
        else return PA; 
    }
}    
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