[Leetcode] 143번 - Reorder List

1. 문제 파악

• 문제 링크: https://leetcode.com/problems/reorder-list/
• 문제: L0 → L1 → … → Ln - 1 → Ln 수열인 연결 리스트를 L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …로 재정렬해라.
• 시간복잡도 파악: 입력크기가 50000이라서 O(nlogn) 이내어야한다.

 

2. 입출력 케이스 도출

• 짝수: [1 2 3 4]
• 홀수: [1], [1 2 3 4 5 6 7]

 

3. 핵심 문제 풀이 도출

 

양쪽 끝 투 포인터(left, right) 사용해서 연결 리스트를 재정렬할수있다. 여기서 left와 right는 기존 리스트의 노드 순서를 가리킨다.

• EX1) [1, 2, 3, 4]
  1. [1, 2, 3, 4]: left = L1, right = L4
     • Logic: L1에 L4을 연결 + L4에 L2를 연결
     • Output: [1, 4, 2, 3, 4]
  2. [1, 4, 2, 3, 4]: left = L2, right = L3
     • Logic: L2에 L3을 연결 + L3 연결 끊기 (null값 저장)
     • Output: [1, 4, 2, 3]
• EX2) [1 2 3 4 5 6 7]
  1. [1 2 3 4 5 6 7]: left = L1, right = L7
     • Logic: L1에 L7을 연결 + L7에 L2를 연결
     • Output: [1 7 2 3 4 5 6]
  2. [1 7 2 3 4 5 6]: left = L2, right = L6
     • Logic: L2에 L6을 연결 + L6에 L3를 연결
     • Output: [1 7 2 6 3 4 5]
  3. [1 7 2 6 3 4 5]: left = L3, right = L5
     • Logic: L3에 L5을 연결 + L5에 L4를 연결
     • Output: [1 7 2 6 3 5 4 5]
  4. [1 7 2 6 3 5 4 5]: left = L4, right = L4
     • Logic: L4에 L4을 연결 + L4에 연결 끊기 (null값 저장)
     • Output: [1 7 2 6 3 5 4]

여기서 핵심 로직은 left 포인터는 맨 처음 노드부터 오른쪽으로 이동시키고 right 포인터는 맨 마지막 노드부터 왼쪽으로 이동시키면서, 기존의 중간 노드까지 도달할때까지 리스트 재정렬이 필요하다.

 

하지만 주어진 리스트는 단방향이므로 맨 마지막 노드에서 역순으로 움직이는 것은 불가하다.

 

연결리스트를 뒤집으면 역순으로 이동할수있어서 해결할수있다. 중간 노드 이후부터 뒤집은 리스트와 기존의 순차적인 리스트와 병합을 수행하면된다. 이는 중간 노드를 찾는 로직과 연결리스트를 뒤집는 로직이 필요하다. Ex) [1, 2, 3, 4, 5, 6] -> reverse list > origin: [1 2 3 4], reverse: [6, 5] -> merge lists -> [1, 6, 2, 5, 3, 4]

 

위의 로직을 생각하고 정확히 작성하는데는 다소 시간이 걸릴거라 생각했다. 그래서 리스트의 노드를 순차대로 입력하고 마지막 입력순으로 출력하는 스택 자료구조를 떠올렸다. 스택을 사용하면 리스트 입/출력이 O(N)이 걸리므로 리스트 병합은 O(1)걸려서 문제를 O(N)으로 풀수있다. Ex) [1, 2, 3, 4, 5, 6] -> stack.push list -> origin: [1, 2, 3], stack: [6, 5, 4] -> merge lists -> [1, 6, 2, 5, 3, 4]

 

4. 코드로 문제 풀이 구현

/**
 * 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; }
 * }
 */

// Using Stack
class Solution {
    // 1. using stack for tracking the last node
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        
        // 1. 스택에 푸시
        ListNode cur = head; 
        Stack<ListNode> stack = new Stack<>();
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }

        // 2. 리스트 노드 개수의 반만 순회하면서 병합
        int size = stack.size();
        ListNode left = head; 
        for (int i = 0; i < size / 2; i++) {
            ListNode right = stack.pop(); // 4, 3
            ListNode next = left.next; // 2, 3
            left.next = right; // 1 -> 4. 2 -> 3
            right.next = next; // 4 -> 2, 3 -> 3
            left = next; // 2, 3
        }

        // 주의: 마지막 노드 처리 (중간 노드의 next를 끊음, 중간노드가 맨 끝으로 감) 
        left.next = null;
    }
}

// Using find mid node and reverse list
class Solution {
    // 1. 중간 노드 찾기  
    // 2. 연결리스트 중간 후반불ㄹ 뒤집기  
    // 3. 두 연결리스트를 재정렬  
    public void reorderList(ListNode head) {  
        if (head == null || head.next == null) return;  
        ListNode midNode = findMidNode(head);  
        ListNode midNextNode = midNode.next;  
        midNode.next = null; // [1 2 3 4], [5, 6]으로 연결리스트 분리 (분리 안하면 맨 마지막 노드가될 4번째 노드가 이전처럼 5번째 노드를 참조한다.)  
        merge(head, reverse(midNextNode));  
    }  

    // 1. 중간 노드 찾기  
    // [1, 2, 3, 4, 5, 6] -> [4]  
    // [1, 2, 3, 4, 5, 6, 7] -> [4]  
    private ListNode findMidNode(ListNode head) {  
        ListNode slow = head, fast = head;  
        while (fast != null && fast.next != null) {  
            fast = fast.next.next;  
            slow = slow.next;  
        }  
        return slow;  
    }  

    // 2. 연결리스트 뒤집기  
    // [1, 2, 3, 4, 5, 6] -> [1 2 3 4], [6, 5]  
    // [1, 2, 3, 4, 5, 6, 7] -> [1 2 3 4], [7, 6, 5]  
    private ListNode reverse(ListNode head) { // slow.next  
        ListNode prev = null, curr = head;  
        // head.next = null;  // [1 2 3 4], [5, 6]으로 연결리스트 분리 (분리 안하면 맨 마지막 노드가될 4번째 노드가 이전처럼 5번째 노드를 참조한다.)  
        while (curr != null) {  
            ListNode nextTemp = curr.next;  
            curr.next = prev;  
            prev = curr;  
            curr = nextTemp;  
        }  
        return prev;  
    }  

    // 3. 재정렬  
    // [1 2 3 4], [6, 5] -> [1, 6, 2, 5, 3, 4]  
    // [1 2 3 4], [7, 6, 5] -> [1, 7, 2, 6, 3, 5, 4]  
    private void merge(ListNode l1, ListNode l2) {  
        while (l2 != null) {  
            ListNode firstNextTemp = l1.next;  
            ListNode seconNextTemp = l2.next;  

            l1.next = l2;  
            l2.next = firstNextTemp;  

            l1 = firstNextTemp;  
            l2 = seconNextTemp;  
        }  
    }
}