LeetCode / Intersection of Two Linked Lists
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:
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.
これもとんち的問題。2つのLinked Listが交わるnodeを返します。
ポイントはNotesのYour code should preferably run in O(n) time and use only O(1) memory.に尽きます。余計な空間計算量は使わずに解を出す必要があります。
解答・解説
解法1
私のsubmitしたコード。計算量オーダーについて条件は満たしていますが、かなり冗長になっています。
2つのポインタを2つのLinked Listの始点から動かし、終点まで移動させます。
このとき先に到着するポインタと後に到着するポインタの移動距離の差をとっておきます。
再度、2つのポインタをLinked Listの始点から動かしますが、このときは後に到着したポインタをさきほどとっておいた差の分だけ先に進めておいてから、2つのポインタをスタートさせます。
そうすると、交わる点があればポインタは必ず出会いますし、逆にポインタが出会わなければ交わる点はない、ということになります。
# 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 """ pa = headA pb = headB diff = 0 if headA is headB: return headA while pa and pb: pa = pa.next pb = pb.next if not pa: while pb: pb = pb.next diff += 1 while diff > 0: headB = headB.next diff -= 1 else: while pa: pa = pa.next diff += 1 while diff > 0: headA = headA.next diff -= 1 while headA and headB: if headA is headB: return headA headA = headA.next headB = headB.next return None
解法2
よりスッキリしたコードがこちら。
2つのポインタを2つのLinked Listの始点から動かし、終点まで移動させるのは同じですが、終点に到達したら、もう一方のLinked Listの始点に移動してさらに動いていくのがミソです。
このようにすると、headA is headBとなった地点を返してやれば、交差するnodeがあればそのnodeが返りますし、交差するnodeがなければnullが返ります。
なるほどですね。。。
class Solution(object): def getIntersectionNode(self, headA, headB): """ :type head1, head1: ListNode :rtype: ListNode """ if headA is None or headB is None: return None pa = headA pb = headB while pa is not pb: pa = headB if pa is None else pa.next pb = headA if pb is None else pb.next return pa