[PS] Leet | 143. 리스트 재배치

문제

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]

조건

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

답

총 세 단계로 나누어 해결합니다.

 

1. 리스트의 중간지점을 찾고

 

2. 중간을 기준으로 뒤쪽 리스트를 반전(reverse)하여

 

3. 앞쪽 리스트와 뒤쪽 리스트를 서로 교차하면서 병합합니다.

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
 */
var reorderList = function(head) {
    let node1 = head;
    let node2 = head;

    // 1. find node1
    while (node2 && node2.next) {
        node2 = node2.next.next;
        node1 = node1.next;
    }

    // 2. reverse the half
    let prev = node1.next;
    node2 = node1;
    node2.next = null;
    while (prev) {
        const tmp = prev.next;
        prev.next = node2;
        node2 = prev;
        prev = tmp;
    }

    // 3. merge
    node1 = head;
    while (node2.next) {
        const node1Next = node1.next;
        const node2Next = node2.next;

        node1.next = node2;
        node2.next = node1Next;

        node1 = node1Next;
        node2 = node2Next;
    }

    return head;
};

시간 복잡도 : O(n)

공간 복잡도 : O(1)