LeetCode 160. Intersection of Two Linked Lists (Easy)

两个链表,可能会有交叉,返回交叉点的元素,若没有交叉则返回null

原始问题

https://leetcode.com/problems/intersection-of-two-linked-lists/

Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:

1
2
3
4
5
A:          a1a2

c1c2c3

B: b1 → b2 → b3

begin to intersect at node c1.

Notes:

  • 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.
  • Your code should preferably run in O(n) time and use only O(1) memory.

解题思路

若将b1节点连接到c3节点后面,此问题就转换为了LeetCode 142. Linked List Cycle II问题,可用相同方法求解,最后断开c3 -> b1的连接即可。LeetCode题解中就是这样做的,不过对此还可以进行优化。

开始时直接设置slowfast指针进行移动,fast指针在移动过程中会遇到null,对此进行处理即可。第一次遇到null时进行连接,若第二次遇到null则说明两个链表没有交叉。其余步骤与LeetCode 142中的做法完全一样,具体见代码。

AC代码

C语言

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
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode * slow, * fast, *p, *tail;

if (!headA || !headB) {
return NULL;
}

slow = headA;
fast = headA;
p = headA;
tail = NULL;

do{
if (!fast->next) {
if (tail) {
tail->next = NULL;
return NULL;
}
fast->next = headB;
tail = fast;
}
if (!fast->next->next) {
if (tail) {
tail->next = NULL;
return NULL;
}
fast->next->next = headB;
tail = fast->next;
}

slow = slow->next;
fast = fast->next->next;
}while(slow != fast);

while (p != slow) {
p = p->next;
slow = slow->next;
}

tail->next = NULL;

return p;
}

相关题目

LeetCode 141. Linked List Cycle (Easy)
LeetCode 142. Linked List Cycle II (Medium)

文章目录
  1. 1. 原始问题
  2. 2. 解题思路
  3. 3. AC代码
    1. 3.1. C语言
  4. 4. 相关题目