問題
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:
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:
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 : / Space :
別解は
Time : / Space :
今後のための考え方
- データ構造を調べたいがために、一度調べやすいかたちに変換して調べてもとに戻す ってのもアリやね