[LeetCode] 143. Reorder List - Java

https://leetcode.com/problems/reorder-list/

Reorder List - LeetCode

---

문제

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln

Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

 

Example 1:

Input: head = [1,2,3,4]
Output: [1,4,2,3]

Example 2:

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]

 

Constraints:

• The number of nodes in the list is in the range [1, 5 * 104].
• 1 <= Node.val <= 1000

---

풀이

풀이 과정

리스트의 head 노드가 주어지고 리스트의 각 노드가 0 → 1 → ... n-1 → n 이라고 할 때 주어진 리스트를 0 → n → 1 → n-1 → ... 의 형태로 재배열하는 문제이다.

문제에서 주어진 조건을 다시 정리하면 리스트의 시작점과 끝점에서부터 각각 노드가 한번씩 교차하도록 재배열을 해야한다. 재배열하기위해 크게 다음 세가지 단계를 거친다.

1. 리스트를 절반으로 나누기
2. 나누어진 리스트 중 뒤의 리스트를 역순 배열하기
3. 나누어진 두 리스트를 번갈아가며 합치기

먼저 리스트를 절반으로 나누기 위해서는 한 칸씩 움직이는 포인터와 두 칸씩 움직이는 두 개의 포인터를 이용한다. 두 칸씩 움직이는 포인터가 리스트의 끝에 도달할 때 한 칸씩 움직이는 포인터의 위치가 리스트의 가운데가 된다.

// 중앙 값을 구하기 위해
// 한 칸씩 움직일 포인터와
// 두 칸씩 움직일 포인터 선언
ListNode slow = head;
ListNode fast = head;

// fast 포인터가 끝에 도착할 때 까지 포인터 이동
while(fast.next != null && fast.next.next != null){
    slow = slow.next;
    fast = fast.next.next;
}

 

다음으로 나누어진 리스트 중 뒤의 리스트를 역순 배열하기 위해서 LeetCode의 206. Reverse Linked의 풀이를 참고하여 리스트를 역순 정렬하는 함수를 작성한다.

[LeetCode] 206. Reverse Linked List - Java

// 리스트 역순 정렬
public ListNode reverseList(ListNode head) {
    // 빈 리스트이거나 다음 노드가 없으면 재귀 호출 종료
    if(head == null || head.next == null){
        return head;
    }

    // 다음 노드 재귀 호출
    ListNode List = reverseList(head.next);

    // 현재 노드의 다음 노드가 가리키는 next 값을 현재 head로 설정
    head.next.next = head;
    // 현재 노드가 가리키는 다음 노드를 null로 설정
    head.next = null;

    // 변경된 List를 return
    return List;
}

 

만들어진 함수를 이용하여 절반으로 나누어진 리스트 중 뒤의 리스트를 역순 정렬하고 slow 포인터의 next를 null로 설정하여 앞의 절반까지의 리스트를 만든다.

// 절반 이후 부터 역순으로 정렬
ListNode list2 = reverseList(slow.next);
// 절반까지의 리스트
slow.next = null;
ListNode list1 = head;

 

 

마지막으로 나누어진 두 개의 리스트를 번갈아가면서 노드를 삽입하여 재졍렬된 리스트를 구한다.

while(list1 != null && list2 != null){
    // 번갈아 가며 노드를 삽입
    ListNode temp = list1.next;
    list1.next = list2;
    list1 = list2;
    list2 = temp;
}

 

리스트의 길이가 2이하인 경우 재정렬을 하는 경우에도 같은 리스트이기 때문에 처음에 조건을 주어 불필요한 연산을 제거한다.

// 리스트의 길이가 2이하 이면 정렬이 불필요하므로 종료
if(head == null || head.next == null || head.next.next == null) return;

 

---

최종 코드

/**
 * 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) {
        // 리스트의 길이가 2이하 이면 정렬이 불필요하므로 종료
        if(head == null || head.next == null || head.next.next == null) return;

        // 중앙 값을 구하기 위해
        // 한 칸씩 움직일 포인터와
        // 두 칸씩 움직일 포인터 선언
        ListNode slow = head;
        ListNode fast = head;

        // fast 포인터가 끝에 도착할 때 까지 포인터 이동
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // 절반 이후 부터 역순으로 정렬
        ListNode list2 = reverseList(slow.next);
        // 절반까지의 리스트
        slow.next = null;
        ListNode list1 = head;
        
        while(list1 != null && list2 != null){
            // 번갈아 가며 노드를 삽입
            ListNode temp = list1.next;
            list1.next = list2;
            list1 = list2;
            list2 = temp;
        }
    }

    // 리스트 역순 정렬
    public ListNode reverseList(ListNode head) {
        // 빈 리스트이거나 다음 노드가 없으면 재귀 호출 종료
        if(head == null || head.next == null){
            return head;
        }

        // 다음 노드 재귀 호출
        ListNode List = reverseList(head.next);

        // 현재 노드의 다음 노드가 가리키는 next 값을 현재 head로 설정
        head.next.next = head;
        // 현재 노드가 가리키는 다음 노드를 null로 설정
        head.next = null;

        // 변경된 List를 return
        return List;
    }
}

---