-
Difficulty: Easy
-
Related Topics: Linked List
-
Link: https://leetcode.com/problems/intersection-of-two-linked-lists/
Description
Write a program to find the node at which the intersection of two singly linked lists begins.
写一个程序，找到两个单链表相交的地方。
For example, the following two linked lists:
例如，以下两个单链表：
begins to intersect at node c1.
在 c1 节点处开始相交。
Examples
Example 1
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.
Example 2
Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Reference of the node with value = 2
Input Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [1,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.
Example 3
Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: null
Input Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.
Notes
-
If the two linked lists have no intersection at all, return
null.如果两个单链表毫无交集，返回
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].链表中每个节点值的范围在
[1, 10^9]。 -
Your code should preferably run in O(n) time and use only O(1) memory.
你的代码最好有 O(N) 时间复杂度和 O(1) 空间复杂度。
Solution
双指针法。起初我很天真的让 p 和 q 两个指针分别在两个链表上跑，这两指针相同了就表示找到了。但这种做法在两链表不相交时就会进入死循环了，得想其它的办法。那么如果让两个指针跑到尽头时，跳到对方的头节点继续跑会怎样呢？实际试了一下，发现此法不仅可行，且这种“换跑道”的操作刚好只执行一次，遂采取这种方法，代码如下：
/**
* Example:
* var li = ListNode(5)
* var v = li.`val`
* Definition for singly-linked list.
* class ListNode(var `val`: Int) {
* var next: ListNode? = null
* }
*/
class Solution {
fun getIntersectionNode(headA:ListNode?, headB:ListNode?):ListNode? {
if (headA == null || headB == null) {
return null
}
var p = headA
var q = headB
while (p != null && q != null) {
// 这里用值相等 `==` 实测也能过
// 不过为了说明“指向同一节点”的语义，这里用引用相等 `===` 更好一点
if (p === q) {
return p
}
p = p.next
q = q.next
// 上面那个“换跑道”的操作，对于不相交的链表，最后 p 和 q 会同时为 null
if (p == null && q == null) {
break
}
// “换跑道”操作
if (p == null) {
p = headB
}
if (q == null) {
q = headA
}
}
return null
}
}
P.S. 相比较解这道题本身，我觉得从样例给的样例输入里构建这种结构似乎还更难一点，有没有读者想挑战一下？（手动狗头）