サンダーボルト

相手モンスターを全て破壊する。

LeetCode Study : 160. 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:

Example 1:

https://assets.leetcode.com/uploads/2018/12/13/160_example_1.png

Input: 
intersectVal = 8, listA = [4,1,8,4,5], 
listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input 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,0,1,8,4,5]. 
There are 2 nodes before the intersected node in A; 
There are 3 nodes before the intersected node in B.

Example 2:

https://assets.leetcode.com/uploads/2018/12/13/160_example_2.png

Input: 
intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Reference of the node with value = 2
Input 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 [0,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.

https://leetcode.com/problems/intersection-of-two-linked-lists/

Note:

  • 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.

自分の解答

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    Set<ListNode> set = new HashSet<>();
    while (headA != null) {
        set.add(headA);
        headA = headA.next;
    }
    while (headB != null) {
        if (set.contains(headB)) {
            return headB;
        }
        headB = headB.next;
    }
    return null;
}

コード理解

別解

public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) {
        return null;
    }

    ListNode tail = headA;
    while (tail.next != null) {
        tail = tail.next;
    }
    tail.next = headB;

    ListNode p1 = headA;
    ListNode p2 = headA;
    while (p2 != null && p2.next != null) {
        p1 = p1.next;
        p2 = p2.next.next;
        if (p1 == p2) {
            ListNode q = p2;
            ListNode k = headA;
            while (q != null) {
                if (q == k) {
                    tail.next = null;
                    return q;
                }
                q = q.next;
                k = k.next;
            }
        }

    }
    tail.next = null;
    return null;
}

とりあえず、BruteForceしなかったことは良かった。ただ、前回学んだループしてたら2つの別速度のポインタ動かせばいいってやつを応用できなかった。

別解ではnodeAの最後にBを自分で連結して2つのポインタを動かす。たしかにこれだと省メモリにつながる。思いつかないなぁ。

自分のは

Time :  O(m+n) / Space :  O(m) or O(n)

別解は

Time :  O(m+n) / Space :  O(1)

今後のための考え方

  • データ構造を調べたいがために、一度調べやすいかたちに変換して調べてもとに戻す ってのもアリやね