8_18 연결 리스트(홀짝 연결리스트)

문제: 홀수 노드 다음에 짝수 노드가 오도록 재구성하기,
조건: 공간복잡도 O(1), 시간 복잡도O(n)

책에는 쉽게 풀 수 있을 것 같은 문제지만 이라는데... 난 전혀 쉬워보지이 않는데... 나만 그런 것인가...? 우선 코드부터 보자.

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        # 예외 처리
        if head is None:
            return None

        odd = head
        even = head.next
        even_head = head.next

        # 반복하면서 홀짝 노드 처리
        while even and even.next:
            odd.next, even.next = odd.next.next, even.next.next
            odd, even = odd.next, even.next

        # 홀수 노드의 마지막을 짝수 헤드로 연결
        odd.next = even_head
        return head

코드를 보고 설명을 보니 딱 와 닿았다.
홀이 odd, 짝이 even일 때 홀수 변수 head, 짝수 변수 head.next이다. 그러니 even_head는 head_next이다.

그리고 while을 사용하여 루프를 돌며 처리한다.

순서     1        2        3
홀수     1-3   3-5         5
짝수     2-4   4-none    none

그리고 마직막에 홀수 1-3-5를 짝수와 이어주면 된다.

odd.next = even_head
return head