Leedcode 160 Intersection of Two Linked Lists

DocumentsAlgorithms
Algorithms, Leetcode, Linked Lists, Python
Catalogue
  1. 1. Question
  2. 2. Analysis
  3. 3. Code

Question

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

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
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.

Analysis

这个问题一般的思路是遍历两个链然后计算两个链表的长度，然后得到两个链表的长度差 n, 然后从长链表的第 n 个节点开始和短链表同时遍历，一一比较各个节点，如果发现相同的节点就说明有交集。这种方法下的时间复杂度为 O(n),而空间复杂度为 O(1)。

另一个思路的复杂度没有变化，不过比较巧妙。分配两个指针 pA 和 pB 分别从头遍历两个链表，并进行一一比较。如果两个链表长度相同，且有交集，则在遍历过程中必然会发现交集；如果两个链表长度不一样但也有交集，则我们使两个指针在遍历到链表末尾后跳到另一个链表头进行第二次遍历，两个指针最后会在第二次遍历时，同时达到交集起点。原因是：两个链表长度不一样时，两个指针在第二次遍历时到达交集起点时所经过的节点数一样，因此两个指针会在第二次遍历时同时到达交集起点。

这里需要注意，若两个链表有交集（intersection），则这两个链表从第一个交集开始，之后所有的节点都一样。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if not headA or not headB:
            return None
        pA = headA
        pB = headB
        while(pA != pB):
            pA = headB if pA is None else pA.next
            pB = headA if pB is None else pB.next
        return pA
Comments