[LeetCode] 328. Odd Even Linked List

https://leetcode.com/problems/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.

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

---

접근 방법

• 짝수번째 노드와 홀수번째 노드를 가리키는 포인터를 만들어 두 노드를 번갈아 순회하면서 새로운 연결 리스트를 만들고, 마지막까지 순회한 후에는 새로 만들어진 홀수 연결 리스트의 뒤에 짝수 연결 리스트를 연결하여 반환한다.

• 공간 복잡도와 시간 복잡도가 제한되므로 새로운 리스트를 만들어 노드의 값을 받아온다던가, 이중 반복문을 사용하는 등의 방식은 제외하고 생각했다.

# 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: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return head
        p_odd = head
        p_even = h_even = head.next
        while p_odd.next and p_odd.next.next:
            p_odd.next, p_even.next = p_odd.next.next, p_even.next.next
            p_odd, p_even = p_odd.next, p_even.next
        p_odd.next = h_even
        return head

• p_odd 와 p_even 두 포인터를 번갈아 진행하여 연결 리스트가 끊어지지 않도록 처리하였다.

• 연결 리스트를 두 리스트로 나눈 후에는 홀수 리스트의 끝에 짝수 리스트의 맨 앞 노드인 h_even 을 연결시켜 반환하였다.

• 이 경우, 전체 연결 리스트를 한 번 순회하므로 시간 복잡도는 $O(n)$이고, 연결 리스트의 특정 노드를 가리키는 포인터만 사용했으므로 공간 복잡도는 $O(1)$이다.