编写一个程序，找到两个单链表相交的起始节点。

解题思路

快慢指针

因为两个链表长度可能不一样，但是相交后的元素都是一样的，可以使用快慢指针

***** 分别遍历链表，获取其长度，长链表命名为quickNode，短链表命名为slowNode，二者长度差为quickStep

***** quickNode先运行quickStep步之后，此时两个链表长度相等，用一个循环就能找到相同起始节点

代码

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
public class Solution {
   public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

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

        int aLength = getLength(headA);
        int bLength = getLength(headB);
        ListNode quickNode = aLength > bLength ? headA : headB;
        ListNode slowNode = aLength > bLength ? headB : headA;
        int quickStep = aLength > bLength ? aLength - bLength : bLength - aLength;

        for (int i = quickStep; i > 0; i--) {
            quickNode = quickNode.next;
        }

        while (quickNode != null) {
            if (quickNode == slowNode) {
                return quickNode;
            }
            quickNode = quickNode.next;
            slowNode = slowNode.next;
        }
        return null;
    }
    
    private int getLength(ListNode head) {
        if(head == null){
            return 0;
        }

        int count = 0;
        ListNode aNode = head;
        while (aNode.next != null) {
            aNode = aNode.next;
            count++;
        }
        return count;
    }
}