[LeetCode] 328. Odd Even Linked List

LeetCode 328. Odd Even Linked List

Odd Even Linked List - LeetCode

Solution

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


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

        cur = head
        root1 = odd = ListNode(0)
        root2 = even = ListNode(0)

        is_odd = True
        while cur:
            if is_odd:
                tmp = ListNode(cur.val)
                odd.next = tmp
                odd = odd.next
            else:
                tmp = ListNode(cur.val)
                even.next = tmp
                even = even.next
            cur = cur.next
            is_odd = not is_odd

        # merge
        odd.next = root2.next

        return root1.next

is_odd라는 bool형 변수를 사용해 홀, 짝을 구분해주어 홀수번째는 odd연결리스트에, 짝수번째는 even연결리스트에 연결해 주었다.
마지막엔 odd의 끝과 even의 처음을 연결해주어 하나의 연결리스트로 합쳤다.
root1.next를 리턴하는 이유는 root1: 0->odd->even 이렇게 구성되어 있기 때문이다.