[leetcode] Reorder List

문제

• 링크
• 단일 연결 리스트(singly linked list)가 주어진다. 아래 형태로 바꿔야 한다.
  • 기존: 1 -> 2 -> 3 -> ... -> n-1 -> n
    변경: 1 -> n -> 2 -> n-1 -> 3 -> ...
• 제약 조건
  • 연결 리스트 길이: [1, 5 * 10^4]
  • 노드 값 범위: 1 <= Node.val <= 1000

풀이

풀기 전

• 어제 풀었던 문제랑 비슷하다. 연결 리스트의 중간 노드를 찾고 중간 이후에 있는 노드들을 알맞게 앞에 채워주면 된다.
• 두 순서로 진행하면 될 거 같다.
  1. 연결 리스트의 중간 노드와 끝 노드 찾기
  2. 중간 지점 이후에 있는 노드들을 역순으로 앞에서부터 채워주기
• 역순으로 채워주기 위해서 stack을 사용했다. 메모리 아끼려면 연결 리스트를 뒤집도록 할 수도 있겠다.
• 연결 리스트 길이를 N이라고 하면 시간 복잡도는 O(N)로 표현할 수 있다. 공간 복잡도도 동일하다.

코드

/**
 * 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 void reorderList(ListNode head) {
        ListNode middle = head, end = head;
        
        // 중간 노드와 끝 노드를 찾는다.
        // 연결 리스트 길이가 짝수이면 end가 null일 때 끝나고, 홀수면 end.next가 null일 때 끝난다.
        while (end != null && end.next != null) {
            middle = middle.next;
            end = end.next.next;
        }

		// 중간 노드 이후에 있는 노드들을 스택에 담아준다.
        Stack<ListNode> stack = new Stack<>();
        ListNode now = middle.next;
        while (now != null) {
            stack.push(now);
            now = now.next;
        }
        // 재배치하면 중간 노드는 항상 맨 뒤에 오므로 next를 null로 만들어준다.
        middle.next = null;
        
        // stack에서 노드 하나씩 뽑으며 앞에서부터 채워준다.
        ListNode a = head, b;
        while (!stack.isEmpty()) {
            b = stack.pop();

            b.next = a.next;
            a.next = b;
            
            a = b.next;
        }
    }
}

푼 후

• 크게 어렵지 않은 문제였다. 아마 연결 리스트 자료구조를 익히는 문제인 거 같다.
• 처음에는 끝에 null 처리를 잘 못해서 순환하는 연결 리스트가 만들어졌다. 가운데 노드의 next를 미리 null로 지정하여 처리할 수 있었다.