XTY的小站
记录技术笔记和技术博客

160. Intersection Of Two Linked List

03 Jul 2024

160. Intersection Of Two Linked List (Easy) 相交链表

题干

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

For example, the following two linked lists begin to intersect at node c1:

The test cases are generated such that there are no cycles anywhere in the entire linked structure.

Note that the linked lists must retain their original structure after the function returns.

Custom Judge:

The inputs to the judge are given as follows (your program is not given these inputs):

The judge will then create the linked structure based on these inputs and pass the two heads, headA and headB to your program. If you correctly return the intersected node, then your solution will be accepted.

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'
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.
- Note that the intersected node's value is not 1 because the nodes with value 1 in A and B (2nd node in A and 3rd node in B) are different node references. In other words, they point to two different locations in memory, while the nodes with value 8 in A and B (3rd node in A and 4th node in B) point to the same location in memory.

Example 2:

Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Intersected at '2'
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: No intersection
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.

Constraints:

Follow up: Could you write a solution that runs in O(m + n) time and use only O(1)memory?

解法

朴素解法

使用额外的备忘录空间，来记录两个链表每个节点的index和内存地址。然后循环短的那个逐个比对。

技巧解法

关键在于补齐路径长度，假设两个链表相交，相交节点之前的长度分别为a和b，相交节点之后的长度为c。

那么最优的情况是a=b，循环一次就能找到相交节点了。但不可能所有的输入都是这种最优的案例，重新思考，我们要的不是a=b，而是在到达相交节点之前，循环的次数是相同的，既然a不是时时等于b，那么循环路径上一定有时时相等的值，比如a+c+b和b+c+a。

所以解法也就出来了，listA的指针，走完ListA本身（a+c）后，继续在ListB上走；ListB的指针，走完ListB本身（b+c）后，继续在ListA上走。如果两者有相交节点的话，两个链表的指针，分别走完b和a个元素后一定会相遇，因为a+c+b等于b+c+a，那么我们就可以在O(m+n)的时间复杂度下找到这个相交节点了

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        cur_a, cur_b = headA, headB
        while cur_a != cur_b:
            # cur_a 走完ListA后，再走ListB
            cur_a = cur_a.next if cur_a else headB
            # cur_b 走完ListB后，再走ListA
            cur_b = cur_b.next if cur_b else headA
        return cur_a