[LeetCode] 328. Odd Even Linked List, Medium

1. 문제

• 단일 연결 리스트가 주어질 때, 값과 상관 없이 첫 번째 인덱스는 홀수, 두 번째 인덱스는 짝수와 같이 쭉 반복되는 형태일 때 홀수 그룹 리스트 + 짝수 그룹 리스트를 연결한 리스트를 반환하라.

2. 해결

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function oddEvenList(head: ListNode | null): ListNode | null {
    let p1 = head;
    let oddList = null, evenList = null; // 두 리스트 참조 값.
    let oddP =null, evenP =null; // 두 리스트 포인터.
    
    let isEven = false; // 홀짝 여부
    
    while(p1) { // p1 전체 탐색.
        const temp = p1.next; // 다음 노드 임시 저장.

        let targetList = isEven ? evenList : oddList; // targetList 참조.
        
        if(!targetList) {	// 리스트가 비어있으면,
            p1.next = targetList;
            targetList = p1; // 리스트 첫 번째 노드 할당.
            
            // 각 리스트 포인터 업데이트.
            if(isEven) evenP = targetList;
            else oddP =targetList;
        } else { // 리스트가 존재하면, 
            p1.next = null; 
            // 홀짝에 맞게 리스트의 마지막을 가리키는 포인터의 다음 노드로 추가.
            if(isEven) {
                evenP.next = p1;
                evenP = p1;
            }
            else {
                oddP.next = p1;
                oddP = p1;
            }
            
        }
                       
        // 각 리스트 할당.
        if(isEven) evenList = targetList;
        else oddList = targetList;
        p1 = temp;
        isEven = !isEven
    }
    // 홀수 리스트의 마지막 포인터 next에 짝수 리스트 연결.
    if(oddP) oddP.next = evenList    
    
    return oddList;
};

• 연결 리스트의 각 노드를 분리해서 두 리스트로 나누어 구성해 붙히는 식으로 작성했다.