160.相交链表
#leetcode#链表 2025-01-26

Problem: 160. 相交链表

思路

首先把两个指针调整到与链表结尾相同的距离，然后一起往后遍历，找到第一个相同的指针，就是第一个公共节点

复杂度

  • 时间复杂度: $O(aLen+bLen)$
  • 空间复杂度: $O(1)$

Code

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
//! 调整到一致的步伐 aLen+bLen,1
class Solution {
public:
  ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    int aLen = 0, bLen = 0;
    ListNode *nodeA, *nodeB;

    nodeA = headA;
    while (nodeA != nullptr) {
      ++aLen;
      nodeA = nodeA->next;
    }
    nodeA = headA;

    nodeB = headB;
    while (nodeB != nullptr) {
      ++bLen;
      nodeB = nodeB->next;
    }
    nodeB = headB;

    if (aLen >= bLen) {
      for (int i = 0; i < aLen - bLen; ++i) {
        nodeA = nodeA->next;
      }
      while (nodeA != nodeB) {
        nodeA = nodeA->next;
        nodeB = nodeB->next;
      }
      return nodeA;
    } else {
      for (int i = 0; i < bLen - aLen; ++i) {
        nodeB = nodeB->next;
      }
      while (nodeA != nodeB) {
        nodeA = nodeA->next;
        nodeB = nodeB->next;
      }
      return nodeA;
    }
  }
};