[LeetCode] #328. Odd Even Linked List

리트코드 #328. 홀짝 연결 리스트

문제

문제 링크

단방향 연결 리스트가 주어졌을 때 홀수 인덱스->짝수 인덱스로 연결해라

풀이

위의 예시만 보면 "노드의 val값에 따라 홀수/짝수를 묶으라는 말인가?" 의문이 들겠지만, 노드의 val값이 아니라 노드의 홀수/짝수 번째 인덱스끼리 연결해야 한다.

홀수 인덱스를 모두 연결한 뒤 짝수 인덱스를 모두 연결할 수 없으므로 홀수, 짝수 하나씩 연결한 후 다음 노드로 이동한다. 빨간색, 파란색, 보라색 포인터는 각각 단계 1, 2, 3에 해당한다.

코드

전체 코드

class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        if head is None:
            return None

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

        # 2칸씩 움직여 홀수, 짝수 인덱스끼리 연결
        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

연결 리스트가 비어있는 경우는 None을 return해 예외처리 한다.
odd는 첫 번째 노드, even과 even_head는 두 번째 노드를 가리키도록 초기화한다.
even은 순차적으로 이동하면서 짝수번째 노드를 가리키며, even_head는 짝수번째 노드들의 시작을 가리킨다.
odd와 even을 모두 연결했다면 홀수번째 노드들 다음으로 짝수번째 노드가 올 수 있도록 odd다음에 even_head가 오도록 만든다.