LeetCode 328 - Odd Even Linked List (Medium)

 

💡 문제

LeetCode - 328번

 

🎯 풀이 과정

O(1) 의 공간 복잡도와 O(n) 의 시간 복잡도를 가지는 알고리즘을 이용해서

홀수번째와 짝수번째에 위치한 노드를 분리한 뒤에 두 리스트를 이어주는 작업을 해야합니다.

리스트의 첫번째 노드는 항상 홀수번째 노드이고 홀수와 짝수는 순서대로 나오는 것은 명백한 사실이니,

제약 조건을 만족하기 위해 한번의 리스트 탐색 도중에 prev 와 cur 포인터를 이용해서

이전 노드의 다음 노드 포인터가 현재 노드의 다음 노드를 가리키도록 변경합니다.

또한 두 리스트를 합치기 위한 mergePointer 도 가장 최신의 홀수번째 노드를 가리키도록 합니다.

 

 

모든 순회를 마치면 mergePointer 로 두 리스트를 이어주면됩니다.

이렇게 하면 입력받는 리스트와 별개로 별도의 메모리공간을 사용하지 않고 해결 가능합니다.

 

👨‍💻 코드

/**
 * 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 {ListNode}
 */
var oddEvenList = function(head) {
    if (!head) {
        return null
    }

    const oddListHead = head
    const evenListHead = head.next

    let order = 1
    let mergeBasePointer = null
    let cur = head, prev = null

    while (cur) {
        const isOdd = order % 2 === 1
        if (isOdd) {
            mergeBasePointer = cur
        }

        // prev pointer 가 있으면 cur.next 로 pointer 를 바꿔준다.
        if (prev) {
            prev.next = cur.next
        }

        order += 1
        prev = cur
        cur = cur.next
    }

    if (mergeBasePointer) {
        mergeBasePointer.next = evenListHead
    }

    return oddListHead
};