链表经典面试题(五)

1.题目

2.详细的图示

3.详细注释和代码实现

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //定义两个表示长度的指针,让它们指向headA和headB
        //我们暂时无法知道哪部分链表长,我们暂且这样定义
        ListNode pl = headA;
        ListNode ps = headB;
        //定义两个长度,来表示以后谁先走差值步
        int len1 = 0;
        int len2 = 0;
        //1.求两个链表的长度
        while(pl != null){
            len1++;
            pl = pl.next;
        }
        while(ps != null){
            len2++;
            ps = ps.next;
        }
        //如果本身就是len1的长度大于len2呢?
        //我们为了求长度,将pl和ps置为了空
        pl = headA;
        ps = headB;
        //我们在求完长度以后,就要比较哪个链表的长度长
        int len = len1-len2;
        if(len < 0){
            //说明len1的长度小于len2
            pl = headB;
            ps = headA;
            len = len2-len1;
        }
        //2.长度长的先走差值步
        while(len != 0){
            pl = pl.next;
            len--;
        }
        //3.两个链表现在长度一致,要一起运动
        while(pl != ps){
            pl = pl.next;
            ps = ps.next;
        }
        //4.相遇的就是公共结点
        //那么如果没有相遇点呢?
        if(pl == null){
            return null;
        }
        return pl;
    }
}
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

找公共结点也得需要考虑特殊情况,希望大家能够跟随博主的脚步,一起学习数据结构.