[리트코드] 18일차

 

138. Copy List with Random Pointer

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        Node dummy = new Node(0);
        Node answer= dummy;
        HashMap<Node, Node> nodeMap = new HashMap<>();

        while (head != null){
            if (!nodeMap.containsKey(head)){
                nodeMap.put(head, new Node(head.val));
            }
            answer.next = nodeMap.get(head);

            if (head.random != null){
                if (!nodeMap.containsKey(head.random)){
                    nodeMap.put(head.random, new Node(head.random.val));
                }
                answer.next.random = nodeMap.get(head.random);
            }

            answer = answer.next;
            head = head.next;
        }
        return dummy.next;
    }
}

문제를 이해하는게 가장 어려웠던 문제다.. 문제가 너무 이해가 안되서 이것저것 찾아보다보니 답을 봐버렸고... 그래서 쉽게 풀 수 있었다..

 

92. Reverse Linked List II

도저히 풀리지 않아서 답을 봤다. 그런데 답을 봐도 이해가 되지 않았다. 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null || left == right){
            return head;
        }

        ListNode dummy = new ListNode(0);
        dummy.next =head;
        ListNode prev = dummy;

        for (int i = 0; i < left - 1; i++){
            prev = prev.next;
        }
        ListNode cur = prev.next;

        for (int i = 0; i < right - left; i ++){
            ListNode temp = cur.next;
            cur.next = temp.next;
            temp.next = prev.next;
            prev.next = temp;
        }
        return dummy.next;
    }
}

저 cur, temp, prev 가 갑자기 어디서 튀어나온것이며, 어떻게 생각해낸 방식인 건지 궁금했다. 그래서 찾아보니많이 쓰는 공식(?) 인 것 같았다.

https://underdog11.tistory.com/entry/JavaScript-22-Generate-Parentheses-1#google_vignette

[JavaScript] 206. Reverse Linked List - 쉬운설명, 인터뷰 필수 문제

 

아래를 참고해서 이해해보려고 했지만... 조금 시간이 걸릴 것 같다

 

완료!