相交链表

题目描述：

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

思路：

统计两个链表的长度l1,l2，然后长的那个先走|l1-l2|步，这时候两个指针一起走，第一个相遇节点就是相交的起始节点，走到最后也没有相等的节点就说明不相交

代码：

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

    int cnt1 = 0;
    int cnt2 = 0;
    ListNode cur1 = headA;
    ListNode cur2 = headB;
//找链表1的长度
    while(cur1!=null){
        cnt1++;
        cur1 = cur1.next;
    }
    //找链表2的长度
    while(cur2!=null){
        cnt2++;
        cur2 = cur2.next;
    }
    cur1 = headA;
    cur2 = headB;
    //让长的那个先走多的部分
    if(cnt1>=cnt2){
        for (int i = 0; i < cnt1-cnt2; i++) {
            cur1=cur1.next;
        }
    }else{
        for (int i = 0; i < cnt2-cnt1; i++) {
            cur2 = cur2.next;
        }
    }
//两个节点一起走
    while(cur1!=null&&cur2!=null){
        if(cur1==cur2){
            return cur1;
        }
        cur1 = cur1.next;
        cur2 = cur2.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