数据结构与算法之链表相交，找交点

链表相交

力扣题目链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists-lcci

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

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

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

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

示例 1：

示例 2：

示例 3：

思路

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

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

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

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

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

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

C++代码如下：

1. class Solution {
2. public:
3. ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
4. ListNode* curA = headA;
5. ListNode* curB = headB;
6. int lenA = 0, lenB = 0;
7. while (curA != NULL) { // 求链表A的长度
8. lenA++;
9. curA = curA->next;
10. }
11. while (curB != NULL) { // 求链表B的长度
12. lenB++;
13. curB = curB->next;
14. }
15. curA = headA;
16. curB = headB;
17. // 让curA为最长链表的头，lenA为其长度
18. if (lenB > lenA) {
19. swap (lenA, lenB);
20. swap (curA, curB);
21. }
22. // 求长度差
23. int gap = lenA - lenB;
24. // 让curA和curB在同一起点上（末尾位置对齐）
25. while (gap--) {
26. curA = curA->next;
27. }
28. // 遍历curA 和 curB，遇到相同则直接返回
29. while (curA != NULL) {
30. if (curA == curB) {
31. return curA;
32. }
33. curA = curA->next;
34. curB = curB->next;
35. }
36. return NULL;
37. }
38. };

• 时间复杂度：
• 空间复杂度：

其他语言版本

Java

1. public class Solution {
2. public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
3. ListNode curA = headA;
4. ListNode curB = headB;
5. int lenA = 0, lenB = 0;
6. while (curA != null) { // 求链表A的长度
7. lenA++;
8. curA = curA.next;
9. }
10. while (curB != null) { // 求链表B的长度
11. lenB++;
12. curB = curB.next;
13. }
14. curA = headA;
15. curB = headB;
16. // 让curA为最长链表的头，lenA为其长度
17. if (lenB > lenA) {
18. //1. swap (lenA, lenB);
19. int tmpLen = lenA;
20. lenA = lenB;
21. lenB = tmpLen;
22. //2. swap (curA, curB);
23. ListNode tmpNode = curA;
24. curA = curB;
25. curB = tmpNode;
26. }
27. // 求长度差
28. int gap = lenA - lenB;
29. // 让curA和curB在同一起点上（末尾位置对齐）
30. while (gap-- > 0) {
31. curA = curA.next;
32. }
33. // 遍历curA 和 curB，遇到相同则直接返回
34. while (curA != null) {
35. if (curA == curB) {
36. return curA;
37. }
38. curA = curA.next;
39. curB = curB.next;
40. }
41. return null;
42. }
44. }

Python

1. class Solution:
2. def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
3. """
4. 根据快慢法则，走的快的一定会追上走得慢的。
5. 在这道题里，有的链表短，他走完了就去走另一条链表，我们可以理解为走的快的指针。
7. 那么，只要其中一个链表走完了，就去走另一条链表的路。如果有交点，他们最终一定会在同一个
8. 位置相遇
9. """
10. cur_a, cur_b = headA, headB # 用两个指针代替a和b
13. while cur_a != cur_b:
14. cur_a = cur_a.next if cur_a else headB # 如果a走完了，那么就切换到b走
15. cur_b = cur_b.next if cur_b else headA # 同理，b走完了就切换到a
17. return cur_a

Go

1. func getIntersectionNode(headA, headB *ListNode) *ListNode {
2. curA := headA
3. curB := headB
4. lenA, lenB := 0, 0
5. // 求A，B的长度
6. for curA != nil {
7. curA = curA.Next
8. lenA++
9. }
10. for curB != nil {
11. curB = curB.Next
12. lenB++
13. }
14. var step int
15. var fast, slow *ListNode
16. // 请求长度差，并且让更长的链表先走相差的长度
17. if lenA > lenB {
18. step = lenA - lenB
19. fast, slow = headA, headB
20. } else {
21. step = lenB - lenA
22. fast, slow = headB, headA
23. }
24. for i:=0; i < step; i++ {
25. fast = fast.Next
26. }
27. // 遍历两个链表遇到相同则跳出遍历
28. for fast != slow {
29. fast = fast.Next
30. slow = slow.Next
31. }
32. return fast
33. }

javaScript

1. var getListLen = function(head) {
2. let len = 0, cur = head;
3. while(cur) {
4. len++;
5. cur = cur.next;
6. }
7. return len;
8. }
9. var getIntersectionNode = function(headA, headB) {
10. let curA = headA,curB = headB,
11. lenA = getListLen(headA),
12. lenB = getListLen(headB);
13. if(lenA < lenB) {
14. [curA, curB] = [curB, curA];
15. [lenA, lenB] = [lenB, lenA];
16. }
17. let i = lenA - lenB;
18. while(i-- > 0) {
19. curA = curA.next
20. }
21. while(curA && curA !== curB) {
22. curA = curA.next;
23. curB = curB.next;
24. }
25. return curA;
26. };

原文链接：https://mp.weixin.qq.com/s/Dmk4qY2W9hn89swPK7_WVQ