개발자 김수진

[문제]

https://leetcode.com/problems/reverse-nodes-in-k-group/description/

[풀이]

문제 설명 (의역)

연결 리스트와 정수 k가 주어졌을 때,리스트를 k개 단위로 묶어서 각 그룹을 뒤집고,
그 결과 리스트를 반환하라.

단:

• 노드 개수가 k보다 작으면 뒤집지 않음
• 노드는 값을 바꾸지 말고 링크를 바꾸라

핵심 아이디어

1. 전체를 k개씩 그룹으로 나누어 처리
2. 각 그룹은 노드 연결을 반전(reverse)
3. 마지막 그룹이 k개보다 작으면 그대로 둠

시간 및 공간 복잡도

• 시간 : O(n). 모든 노드 한번씩 순회
• 공간 : O(1). 재귀 안 쓰고 포인터만 사용함

[코드]

/**
 * 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 reverseKGroup(ListNode head, int k) {

        if(head == null || k == 1)  return head;

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

        ListNode prevGroupEnd = dummy;

        while(true) { 
            ListNode kth = getKth(prevGroupEnd , k);
            if(kth == null) break;

            ListNode start = prevGroupEnd.next;
            ListNode nextGroupStart = kth.next;

            ListNode prev = nextGroupStart;
            ListNode cur = start;

            while(cur != nextGroupStart) {
                ListNode temp = cur.next;
                cur.next = prev;
                
                prev = cur;
                cur = temp;
            }

            prevGroupEnd.next = kth;
            prevGroupEnd = start;
        }

        return dummy.next;
        
    }

    public ListNode getKth(ListNode node, int k) {
        while(node != null && k > 0) {
            node = node.next;
            k--;
        }
        return node;
    }
}

[문제]

https://leetcode.com/problems/merge-k-sorted-lists/

[풀이]

문제 요약

k개의 정렬된 연결 리스트가 주어진다.이들을 하나의 정렬된 연결 리스트로 병합(merge) 하라.

핵심 아이디어

k개의 정렬된 리스트를 병합할 때, 가장 효율적인 방법은:

각 리스트의 가장 작은 원소를 힙(min-heap)에 넣고,매번 가장 작은 값을 꺼내서 연결 리스트로 구성하는 것

시간/공간 복잡도

• 시간 : O(N log k). N: 전체 노드 수, k: 리스트 개수
  • 노드 1개 꺼내기 + 다음 노드 삽입 : O( log k).
• 공간: O(k). 힙에 최대 k개 노드 존재

[코드]

/**
 * 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 mergeKLists(ListNode[] lists) {

        PriorityQueue<ListNode> pq = new PriorityQueue<>(
            (a,b) -> Integer.compare(a.val , b.val)
        );

        for(ListNode node : lists) {
            if(node != null)   pq.offer(node);
        }

        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;

        while(!pq.isEmpty()) {
            ListNode node = pq.poll();

            cur.next = node;
            cur = cur.next;

            if(node.next != null)   pq.offer(node.next);

        }
        return dummy.next;
    }
}

[문제]

https://leetcode.com/problems/lru-cache/

[풀이]

capacity(최대 용량)을 갖는 캐시(Cache)를 구현하라.
다음 두 연산을 O(1) 시간 안에 처리해야 한다:

연산

1. get(key)
   • 키가 캐시에 있으면 값을 반환
   • 없으면 -1 반환
   • 단, 사용된 것으로 간주해 가장 최근에 사용한 위치로 갱신됨
2. put(key, value)
   • 키가 이미 있다면 값을 갱신하고, 가장 최근으로 간주
   • 키가 없다면 새로 넣되,캐시가 가득 찼으면 가장 오래된(Least Recently Used) 항목을 제거

 핵심 요구사항

• O(1) 시간 복잡도
• 즉, HashMap + Doubly Linked List 조합이 필요

[코드]

class LRUCache {

    class Node {
        int key, val;
        Node next, prev;

        Node(int k, int v) {
            key = k;
            val = v;
        }
    }

    int capacity;
    Map<Integer, Node> map;
    Node head, tail;

    public LRUCache(int capacity) {

        this.capacity = capacity;
        map = new HashMap<>();

        head = new Node(0,0);
        tail = new Node(0,0);

        head.next = tail;
        tail.prev = head;
        
    }
    
    public int get(int key) {
        Node node = map.get(key); 

        if(node == null ) return -1;
        moveToFront(node);

        return node.val;
    }
    
    public void put(int key, int value) {
        Node node = map.get(key);
        if(node != null) {
            node.val = value;
            moveToFront(node);

        } else {
            if(map.size() == capacity) {
                removeEnd();
            }
            Node newNode = new Node(key, value);
            map.put(key, newNode);
            addToFront(newNode);
        }

    }
    public void moveToFront(Node node) {

        node.next.prev = node.prev;
        node.prev.next = node.next;
        addToFront(node);
    }

    public void addToFront(Node node) {
        node.next = head.next;
        head.next.prev = node;

        node.prev = head;
        head.next = node; 
    }


    public void removeEnd() {
        Node node = tail.prev;

        map.remove(node.key);

        Node prev = node.prev;

        prev.next = tail;
        tail.prev = prev;

    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

[문제]

https://leetcode.com/problems/copy-list-with-random-pointer/description/

[풀이]

이 리스트를 깊은 복사(deep copy)해서 새로 만들고, 그 새 리스트의 head를 반환하라.

깊은 복사란?

• 원본 리스트와 완전히 독립적인 새 리스트여야 함
• 각 노드는 새롭게 생성되어야 하며,
• next, random도 원본과 같은 구조로 연결돼야 함

핵심 아이디어:
원본 노드 → 복사본 노드 간 매핑을 HashMap에 저장해놓고, 두 번째 순회에서 next, random을 연결

시간 및 공간 복잡도

• 시간 : O(n). 리스트 전체 두번 순회
• 공간 : O(n). HashMap에 n개의 노드 저장

[코드]

/*
// 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) {

        Map<Node, Node> nodeMap = new HashMap<>();
        Node cur = head;

        while(cur!=null) {
            nodeMap.put(cur, new Node(cur.val));
            cur = cur.next;
        }

        cur = head;
        while(cur != null) {
            Node copy = nodeMap.get(cur);
            copy.next = nodeMap.get(cur.next);
            copy.random = nodeMap.get(cur.random);
            cur = cur.next;
        }

        return nodeMap.get(head);
        
    }
}

[문제]

https://leetcode.com/problems/linked-list-cycle-ii/

[풀이]

문제 요약

연결 리스트가 주어졌을 때,

1. 사이클이 존재하는지 확인하고,
2. 존재하면 그 사이클이 시작되는 노드를 반환하라.

핵심 알고리즘: Floyd’s Cycle Detection 

1. 사이클 존재 여부 감지

• slow, fast 포인터 (1칸, 2칸씩 이동)
• 둘이 만나면 사이클 존재

2. 만난 후에, head부터 다시 한 포인터 출발

• 새 포인터와 slow를 1칸씩 이동
• 처음 만나는 곳이 사이클의 시작점

왜 이렇게 하면 되나? (수학적 설명)

• slow와 fast가 만난 지점까지의 거리: a + b
  • a = head → 사이클 시작까지 거리
  • b = 사이클 시작 → 만난 지점까지 거리
• fast는 2배 속도 → 수식 유도:

  2(a + b) = a + b + n*c → a = c - b

  n*c는 사이클을 n번 돌았다는 뜻
  사이클 사이즈 만큼 앞서야 slow,fast가 만나므로
• 즉, head에서 출발한 포인터와, 만난 지점에서 출발한 slow가 → 사이클 시작점에서 동시에 만남

a = c-b

위의 식에서 head에서부터 사이클 시작점까지의 거리는 , 만난 위치에서 사이클의 나머지만큼 돌면 시작점에서 만난다는걸 알 수 있다.

[코드]

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast  = head;

        while(fast!=null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if(slow == fast) {

                ListNode ptr = head;
                while ( ptr != slow ) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
                
            }
        }

        return null;
        
    }
}

[문제]

https://leetcode.com/problems/sort-list/description/

[풀이]

단일 연결 리스트가 주어졌을 때, 오름차순 정렬된 리스트를 반환하라.
시간 복잡도는 O(n log n)이어야 하고, 상수 공간 사용(즉, O(1) 추가 메모리)이어야 한다.

핵심 아이디어

• 연결 리스트에서는 퀵정렬보다 병합 정렬이 더 적합 → 이유: 중간 분할이 쉽고, random access가 불가능하므로

전체 과정 요약:

1. 리스트를 반으로 나눈다 (slow/fast 포인터)
2. 각각 정렬된 리스트로 재귀 정렬
3. 두 리스트를 병합(merge)

시간 및 공간 복잡도

• 시간 : O(n log n). 반으로 나누기 (log n) × merge (n)
• 공간 : O(1)

[코드]

/**
 * 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 sortList(ListNode head) {

        if(head == null || head.next == null)   return head;

        ListNode mid = findMid(head);
        ListNode right = mid.next;
        mid.next = null;

        ListNode leftSorted = sortList(head);
        ListNode rightSorted = sortList(right);

        return mergeList(leftSorted, rightSorted);
    }

    private ListNode mergeList(ListNode node1 , ListNode node2) {
        ListNode mergedList = new ListNode(0);
        ListNode cur = mergedList;
        
        while(node1 != null && node2 != null) {

            if(node1.val < node2.val) {
                cur.next=node1;
                node1 = node1.next;
            } else {
                cur.next = node2;
                node2 = node2.next;
            }
            cur = cur.next;
        }
        cur.next = (node1 == null) ? node2 : node1;
        return mergedList.next;
    }

    private ListNode findMid(ListNode head) {
        ListNode fast = head.next;
        ListNode slow = head;
        
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        return slow;
    }
}

[문제]

https://leetcode.com/problems/swap-nodes-in-pairs/description/

[풀이]

연결 리스트가 주어질 때, 인접한 두 노드를 쌍으로 묶어서 위치를 서로 바꾸라.
단, 노드 자체를 바꾸는 것이지, 값만 바꾸는 게 아니다.

핵심 풀이

• 한 번에 두 개씩 묶어서 처리: first, second
• 그 다음 노드들과의 연결을 잘 이어야 함
• head가 바뀔 수도 있으니 dummy 노드 사용하는 게 안전

시간 및 공간 복잡도

• 시간 복잡도: O(n) (노드 한 번씩 방문)
• 공간 복잡도: O(1) (추가 메모리 거의 없음)

[풀이]

/**
 * 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 swapPairs(ListNode head) {

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

        ListNode prev = dummy;

        while(prev.next!=null && prev.next.next != null) {

            
            ListNode first = prev.next;
            ListNode second = first.next;

            first.next =second.next;
            second.next = first;

            prev.next= second;

            prev = first;
            
        }

        return dummy.next;
    }
}

[문제]

https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/

[풀이]

단일 연결 리스트에서 뒤에서 n번째 노드를 삭제하고, 수정된 리스트의 head를 반환하라.

두 포인터(tail-gap 방식)

1. fast 포인터를 n만큼 먼저 이동시킨다.
2. slow 포인터와 fast 포인터를 같이 이동한다.
3. fast가 끝(null)에 도달했을 때, slow는 삭제 대상 앞에 위치한다.
4. slow.next = slow.next.next로 삭제

시간 / 공간 복잡도

• 시간 : O(n). 리스트 전체 한번 탐색
• 공간 : O(1). 포인터만 사용

[코드]

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 더미 노드 (head 삭제도 커버하기 위해)
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode fast = dummy;
        ListNode slow = dummy;

        // fast를 n+1칸 먼저 이동 (slow가 삭제 전 노드에 서기 위해)
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }

        // fast와 slow 같이 이동
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // slow.next가 삭제 대상
        slow.next = slow.next.next;

        return dummy.next;
    }
}