[LeetCode, Python] 328. 홀짝 연결 리스트(Odd Even Linked List)

연결 리스트를 홀수 노드 다음에 짝수 노드가 오도록 재구성하라.

공간 복잡도 O(1), 시간 복잡도 O(n)에 풀이하라.

 

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

Output: [1,3,5,2,4]

 

 

** 깔끔한 풀이 **

 

 

1. 반복 구조로 홀짝 노드 처리

 

 

# 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 head is None:
            return None
        
        odd, even = head, head.next
        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

 

 

해설:

 

홀수 노드, 짝수 노드로 리스트를 연결해가다가

마지막에 홀수 노드의 끝을 짝수 노드의 시작점을 가리키면 될 것 같다!

 

연결 리스트만 일주일 동안 풀어서 대충 이러한 방식으로 풀면 될 것 같다가 슬슬 나온다.

 

다중 할당을 이용하여 코드를 좀 더 깔끔하게 해 준다.

(여기서는 다중 할당을 일부러 쓸 필요는 없다)