Leetcode-160 Intersection of Two Linked Lists

发表于 | 分类于 | 次

Intersection of Two Linked Lists

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

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.

解题思路

链表 A 长度：a+c，链表 B 长度：b+c；c 为相同部分的长度，没有交点时，c 为 0。因为 a+c+b=b+c+a，所以让 p 指针从链表 A 出发，当 p 为 null 时，走了 a+c 步，此时让 p 继续从 B 出发；同理，让 q 从 B 出发，为 null 再从 A 出发。 之后 p 和 q 一定会在交点处相遇，若没有交点，p==q==null。

复杂度分析

  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$

代码

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
	ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
		ListNode *p = headA, *q = headB;
		while (p != q) {
			p = p ? p->next : headB;
			q = q ? q->next : headA;
		}
		return p;
	}
};