HomeAboutMeBlogGuest
© 2025 Sejin Cha. All rights reserved.
Built with Next.js, deployed on Vercel
👻
개발 기록/
코딩테스트 스터디
코딩테스트 스터디/
Reorder List

Reorder List

Link
https://leetcode.com/problems/reorder-list/
Deadline
Dec 13, 2022
Status
Archived
Type
linked list
Two-Pointer
recursion

문제

You are given the head of a singly linked-list. The list can be represented as:
Reorder the list to be on the following form:
You may not modify the values in the list's nodes. Only nodes themselves may be changed.
notion image
Constraints:
  • The number of nodes in the list is in the range [1, 5 * 104].
  • 1 <= Node.val <= 1000
 

풀이

효성
재영
L0 → L1 → … → Ln - 1 → Ln
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

/**
 * 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 cur = head;
    let size = 0;
    
    while (cur) {
        size += 1;
        cur = cur.next;
    }

    const reorderArr = Array(size);
    const mid = parseInt((size - 1) / 2);
    let idx = 0;
    cur = head;

    while(cur) {
        if(idx === 0) {
            reorderArr[0] = cur.val;
        }
        else if(idx <= mid) {
            reorderArr[idx * 2] = cur.val;
        }
        else {
            const idxAfterMid = idx - (mid + 1);
            const decrement = idxAfterMid * 2;
            if(size % 2 === 0) {
                reorderArr[size - 1 - decrement] = cur.val;
            }
            else {
                reorderArr[size - 2 - decrement] = cur.val;
            }
        }

        cur = cur.next;
        idx += 1;
    }
    
    cur = head;
    idx = 0;

    while (cur) {
        cur.val = reorderArr[idx];
        idx += 1;
        cur = cur.next;
    }
};
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }

 * 1. 일단 주어진 노드 개수는 10000개. 따라서 O(N ^ 2)를 만족하면 된다.
 * 2. 많은 방법이 있겠지만, 나는 메모이제이션을 활용했다. 결국 노드를 각각 캐싱하면 문제는 쉽게 풀린다.
 * 3. 따라서 시간 복잡도 O(N) 공간 복잡도 O(N)이면 주어진 문제를 쉽게 달성할 수 있다.
 */
/**
 * @param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
 */
var reorderList = function(head) {
    let node = head;
    const memo = []; // 바꿔주기 위한 배열
    
    while (node !== null) {
        const now = node;
        memo.push(now)

        node = now.next;
        now.next = null; // 사이클을 만들지 않기 위해
    }

    const nodeLength = memo.length;

    const reorders = []; // 바꿔주기 위한 대상
    while (memo.length > Math.ceil(nodeLength / 2)) {
        reorders.push(memo.pop())
    }

    const reorderedArr = reorder(memo, reorders);

    reorderOriginalHead(reorderedArr);
};

function reorder(memo, reorders) {
    const res = [];
    for (let i = 0; i < reorders.length; i += 1) {
        res.push(memo[i]);
        res.push(reorders[i]);
    }

    if (memo.length !== reorders.length) {
        res.push(memo.pop())
    }

    return res;
}

function reorderOriginalHead(arr) {
    let head = arr[0];

    for (let i = 1; i < arr.length; i += 1) {
        const nextNode =arr[i];
        
        head.next = nextNode;
        head = nextNode;
    }
}