0%

[Leetcode]160. Intersection of Two Linked Lists(C++)

题目描述

题目链接:160. Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

例子

见官网示例。

Follow Up

Note

  • If the two linked lists have no intersection at all, return null.
  • The linked lists must retain their original structure after the function returns.
  • You may assume there are no cycles anywhere in the entire linked structure.
  • Each value on each linked list is in the range [1, 10^9].
  • Your code should preferably run in O(n) time and use only O(1) memory.

解题思路

如果两个链表长度一样的话很简单,只需要一次遍历逐个比较节点是否相同即可,发现第一个节点相同时就返回该节点。但是链表长度不一样,因此我们可以先遍历一次获得两个链表的长度,再计算其长度差 n,再在较长的链表先遍历 n 步,然后再逐个节点比较即可。

代码如下:

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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (!headA || !headB) {
return nullptr;
}

int lenA = 0;
int lenB = 0;
ListNode *currA = headA;
ListNode *currB = headB;

// 计算长度
while (currA) {
lenA++;
currA = currA->next;
}
while (currB) {
lenB++;
currB = currB->next;
}

currA = headA;
currB = headB;
while (currA && currB) {
// A B 遍历的节点先同步位置
if (lenA > lenB) {
currA = currA->next;
lenA--;
} else if (lenB > lenA) {
currB = currB->next;
lenB--;
}
else {
// 比较 A B 节点是否相同
if (currA == currB) {
return currA;
}
currA = currA->next;
currB = currB->next;
}
}

return currA;
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

GitHub 代码同步地址: 160.IntersectionOfTwoLinkedLists.cpp

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions