[리트코드] 328. Odd Even Linked List

# 문제 설명

연결리스트가 주어질 때, 짝수 번째 인덱스가 홀수 번째 인덱스 뒤에 오도록 재정렬하여 반환해라.

 

# 입출력 예시

입력	출력
1 -> 2 -> 3 -> 4 -> 5	1 -> 3 -> 5 -> 2 -> 4

 

# 코드 풀이 1. 재귀로 풀이

from copy import copy

class Solution:
    def getOddnEven(self, now: Optional[ListNode]) -> Optional[ListNode]:
        rev = None
        if now and now.next:
            rev, rev.next = copy(now.next), rev
            now.next, rev.next = self.getOddnEven(now.next.next)
        return now, rev # 순방향, 역방향
    
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        odd, even = self.getOddnEven(head)
        now = odd
        if now:
            while now.next != None:
                now = now.next
            now.next = even # 홀수 끝에 짝수 연결
        return odd

 

# 코드 풀이 2. 반복으로 풀이

class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None:
            return None
        
        odd = head
        even_head = even = head.next
        while even and even.next:
            odd.next, even.next = even.next, even.next.next
            odd, even = odd.next, even.next
        odd.next = even_head # 홀수 뒤에 짝수
        return head

 

 

# 핵심 포인트

• 홀수 번째 노드와 짝수 번째 노드를 따로 처리해야 한다. 또 두 노드를 이어주어야 한다.
  • 재귀 호출을 이용하여, 홀수 번째는 순서대로, 짝수 번째는 역으로 연결하여 이어준다.
  • 처음 노드를 저장해두어, 홀수 번째와 짝수 번째 모두 순서대로 연결하여 이어준다.