[코테] 리트코드 연결 리스트 328. Odd Even Linked List

328. Odd Even Linked List

문제 링크

https://leetcode.com/problems/odd-even-linked-list/description/

문제 설명

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.

You must solve the problem in O(1) extra space complexity and O(n) time complexity.

제한 사항

• The number of nodes in the linked list is in the range [0, 10^4].
• -10^6 <= Node.val <= 10^6

입출력 예 #1

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

입출력 예 #2

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

문제 풀이

반복하면서 홀수 노드와 짝수 노드를 각각 연결시킨 이후 홀수 노드의 마지막을 짝수 노드의 헤드로 연결한다.

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

        odd = head
        even = 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