솔루션: 두 연결 목록의 교차점

이것은 일련의 Leetcode 솔루션 설명( )의 일부입니다. 이 솔루션이 마음에 들었거나 유용하다고 생각되면 이 게시물에 좋아요를 누르거나 찬성 투표my solution post on Leetcode's forums를 해주세요.

Leetcode 문제 #160(쉬움): 두 연결 목록의 교차점

설명:

(다음으로 이동: Solution Idea || 코드: JavaScript | Python | Java | C++ )

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.

예:

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
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.
Visual:

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
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.
Visual:

Example 3:
Input:	intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output:	null
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. The two lists do not intersect, so return null.
Visual:

제약:

• 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.
• Each value on each linked list is in the range [1, 10^9].
• Your code should preferably run in O(n) time and use only O(1) memory.

아이디어:

(다음으로 이동: Problem Description || 코드: JavaScript | Python | Java | C++ )

순진한 접근 방식은 동일한 노드를 두 번 볼 때까지 각 노드 참조를 데이터 구조에 저장하는 것이지만 O(N) 추가 공간이 필요합니다.

O(1) 추가 공간만으로 이 문제를 해결하려면 두 연결 목록을 정렬하는 다른 방법을 찾아야 합니다. 더 중요한 것은 두 목록의 끝을 정렬하는 방법을 찾아야 한다는 것입니다. 가장 쉬운 방법은 A+B와 B+A의 반대 순서로 연결하는 것입니다. 이렇게 하면 원래 두 목록의 끝이 병합된 각 목록의 후반부에 정렬됩니다.





그런 다음 어떤 지점에서 병합된 두 목록이 동일한 노드를 가리키는지 확인하면 됩니다. 사실 두 개의 병합된 리스트가 교차하지 않더라도 병합된 리스트의 끝에 도달했을 때 a와 b의 값은 동일(null)하므로 이를 종료 조건으로 사용할 수 있습니다.

목록 중 하나(둘 다는 아님)가 끝나는 경우 headB를 a에 문자열로 연결하고 그 반대의 경우도 마찬가지입니다.

구현:

네 가지 언어 모두에 대한 코드가 거의 동일합니다.

자바스크립트 코드:

(다음으로 이동: Problem Description || Solution Idea )

var getIntersectionNode = function(headA, headB) {
    let a = headA, b = headB
    while (a !== b) {
        a = !a ? headB : a.next
        b = !b ? headA : b.next
    }
    return a
};

파이썬 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        a, b = headA, headB
        while (a != b):
            a = headB if not a else a.next
            b = headA if not b else b.next
        return a

자바 코드:

(다음으로 이동: Problem Description || Solution Idea )

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA, b = headB;
        while (a != b) {
            a = a == null ? headB : a.next;
            b = b == null ? headA : b.next;
        }
        return a;
    }
}

C++ 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *a = headA, *b = headB;
        while (a != b) {
            a = !a ? headB : a->next;
            b = !b ? headA : b->next;
        }
        return a;
    }
};