代码随想录—力扣算法题：07.链表相交. Java版（示例代码与导图详解）

版本说明

当前版本号[20230923]。

07. 链表相交

同：160.链表相交

力扣题目链接

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

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

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

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

示例 1：

示例 2：

示例 3：

思路

简单来说，就是求两个链表交点节点的指针。 这里同学们要注意，交点不是数值相等，而是指针相等。

为了方便举例，假设节点元素数值相等，则节点指针相等。

看如下两个链表，目前curA指向链表A的头结点，curB指向链表B的头结点：

我们求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置，如图：

此时我们就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点。

否则循环退出返回空指针。

代码实现

1、首先，我们需要找到两个链表的长度。我们可以通过遍历链表来实现这一点。在遍历过程中，我们将链表A的长度存储在变量lenA中，将链表B的长度存储在变量lenB中。

	ListNode curA = headA;
        ListNode curB = headB;
        int lenA = 0;
        int lenB = 0;

        while(curA != null){	// 求链表A的长度
            lenA++;
            curA = curA.next;
        }

        while(curB != null){	// 求链表B的长度
            lenB++;
            curB = curB.next;
        }

        curA = headA;
        curB = headB;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2、然后，我们需要确保链表A是较长的链表。如果链表B的长度大于链表A的长度，我们需要交换它们的长度和头节点。这是因为我们在后续的遍历中将从链表A的末尾开始，而从链表B的头部开始。

 // 让curA为最长链表的头，lenA为其长度
        if(lenB > lenA)
        {
            int tmplen = lenA;
            lenA = lenB;
            lenB = tmplen;
            ListNode tmpNode = curA;
            curA = curB;
            curB = tmpNode;
        }
1
2
3
4
5
6
7
8
9
10

3、接下来，我们需要计算两个链表的长度差。这将用于确定我们需要从链表A的末尾移动到何处，以便与链表B对齐。

 // 求长度差
        int gap = lenA - lenB;
1
2

4、然后，我们需要让链表A和链表B在同一起点上（即它们的末尾位置对齐）。我们可以通过从链表A的末尾向前移动lenA - lenB个节点来实现这一点。

// 让curA和curB在同一起点上（末尾位置对齐）
        while(gap-- > 0)
        {
            curA = curA.next;
        }
1
2
3
4
5

5、最后，我们需要遍历链表A和链表B，直到找到相同的节点（即交点）。如果找到相同的节点，我们将立即返回该节点。如果我们遍历完两个链表都没有找到交点，我们将返回null。

// 遍历curA 和 curB，遇到相同则直接返回
        while(curA != null)
        {
            if(curA == curB)
            {
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
1
2
3
4
5
6
7
8
9
10

总结

​ 这段代码的主要功能是找到两个链表的交点。首先，它通过遍历链表来获取链表A和链表B的长度。然后，如果链表B的长度大于链表A的长度，它会交换这两个长度，并交换相应的头节点。接着，它会计算两个链表的长度差，并根据这个长度差从链表A的末尾向前移动相应的节点，使得链表A和链表B在同一起点上。最后，它会遍历链表A和链表B，一旦找到相同的节点，就立即返回该节点。如果遍历完两个链表都没有找到交点，它将返回null。

完整代码：

public class Day09
{
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        int lenA = 0;
        int lenB = 0;

        while(curA != null){
            lenA++;
            curA = curA.next;
        }

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

        curA = headA;
        curB = headB;

        // 让curA为最长链表的头，lenA为其长度
        if(lenB > lenA)
        {
            int tmplen = lenA;
            lenA = lenB;
            lenB = tmplen;
            ListNode tmpNode = curA;
            curA = curB;
            curB = tmpNode;
        }

        // 求长度差
        int gap = lenA - lenB;

        // 让curA和curB在同一起点上（末尾位置对齐）
        while(gap-- > 0)
        {
            curA = curA.next;
        }

        // 遍历curA 和 curB，遇到相同则直接返回
        while(curA != null)
        {
            if(curA == curB)
            {
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }

        return null;
    }
}
l)
        {
            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
57
58
59
60
61
62
63
64
65
66
67
68