LeetCode/Intersection of Two Linked Lists

( 블로그 기사 의 전재)

[ h tps : // / ㅇ t 여기. 코 m / p 로b ㎇ ms / 어서 r세 c 치온 - f-와 ぉ ㅅ ]

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.

이것도 터치적 문제. 두 개의 링크 된 목록이 교차하는 노드를 반환합니다.
포인트는 Notes의 Your code should preferably run in O(n) time and use only O(1) memory. 불필요한 공간 계산량은 사용하지 않고 해를 내야합니다.

해답·해설

해법 1

내 제출한 코드. 계산량 주문에 대한 조건은 충족되지만 상당히 중복됩니다.

2개의 포인터를 2개의 Linked List의 시점으로부터 이동해, 종점까지 이동시킵니다.
이 때 먼저 도착하는 포인터와 나중에 도착하는 포인터의 이동 거리의 차이를 취해 둡니다.
다시 두 개의 포인터를 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가 headB가 된 지점을 반환하면 교차하는 노드가 있으면 해당 노드가 반환되고 교차하는 노드가 없으면 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