개요

LeetCode #328, Odd Even Linked List 문제를 풀어봅니다.

Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.

The first node is considered odd, and the second node is even, and so on.

Note that the relative order inside both the even and odd groups should remain as it was in the input.

Example 1:

Input: head = [1,2,3,4,5] Output: [1,3,5,2,4]

Example 2:

Input: head = [2,1,3,5,6,4,7] Output: [2,3,6,7,1,5,4]

Constraints:

• The number of nodes in the linked list is in the range [0, 104].
• -106 <= Node.val <= 106

Follow up: Could you solve it in O(1) space complexity and O(nodes) time complexity?

홀수 노드 다음 짝수 노드가 와야 하니 odd, even 각각을 구성하고 odd의 마지막에 even의 처음을 연결하면 될 것입니다. 입력이 1->2->3->4->5인 연결 리스트라면 홀수 변수(odd)는 head, 짝수 변수(even, even_head)는 head.next입니다. 홀수 변수는 다음 홀수 변수로 가야 하니 odd.next를 odd.next.next로 해서 2칸 건너뛰도록 하고, even.next도 even.next.next로 해서 2칸 건너뛰도록 홀짝 처리를 같이 합니다. odd와 even은 한 칸씩 움직여서 다움 반복을 돌 수 있도록 합니다. 1회 반복 시 홀수는 1->3, 짝수는 2->4, 2회 반복 시 홀수는 3->5, 짝수는 4->None, 3회 반복 시 홀수는 5, 짝수는 None인 상태인데, 이 때 반복이 끝나고 5가 짝수의 head인 2와 연결이 됩니다. 1->3->5->2->4->None이 됩니다.

# 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:
        # exception
        if head is None:
            return None
        
        odd = head
        even = head.next
        even_head = head.next
        
        # keep going: odd-even-odd-even-...
        while even and even.next:
            odd.next, even.next = odd.next.next, even.next.next
            odd, even = odd.next, even.next
        
        # final odd -> even_head
        odd.next = even_head
        
        return head