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

파이썬으로 배우는 알고리즘 책을 공부하며 풀었던 LeetCode문제들을 재정리해보자.

 

# 문제 설명 

328번 Odd Even Linked List는 입력받은 연결 리스트를 홀수 번째 노드 다음에 짝수 번째 노드가 오도록 재구성하는 문제이다.

Example

 

 

# 풀이방법 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: Optional[ListNode]) -> Optional[ListNode]:
    
        root = result = ListNode() 
        
        odd = [] # 홀수 
        even = []  # 짝수
        
        cnt = 1
        
        if head is None :
            return head
        
        # 연결리스트를 순회하며 홀수번째와 짝수번째인지에 따라 값을 저장한다. 
        while head :
            if cnt %2 == 1 :
                odd.append(head.val)
            else :
                even.append(head.val)
                
            head = head.next
            cnt +=1 
        
        # 홀수와 짝수값 리스트를 합친다.
        odd += even
    
        # 리스트를 연결리스트로 변환
        for idx in range(0, cnt-1) :
            result.val = odd[idx] 
            if idx != cnt-2 :
                result.next = ListNode()
                result = result.next
            
        return root

| 아이디어 및 흐름 |

연결리스트를 while문으로 순회하며, 홀수번째와 짝수번째의 값들을 각각의 리스트로 저장 후, 두 리스트를 합쳐 다시 연결리스트로 변환한다. 

1. 주어진 연결리스트가 빈 리스트인지 확인한다.

2. 연결리스트를 while문으로 순회하며, 홀수번째와 짝수번째의 값들을 각각의 리스트로 저장한다.

3. 두 리스트를 합치고, 합친 리스트를 연결리스트로 만든다.

 

하지만 위 풀이는 편법적인 풀이고, 책 저자는 이는 우아하지 않는 풀이법이라고 하였다. 또한 오프라인 코딩 테스트에서는 지적받을 수 있다고 한다. 

 

# 풀이 방법 2 - 반복 구조로 홀짝 노드 처리 (책 풀이 참고)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        
        # 예외 처리 
        if head is None :
        	return None
            
        odd = head
        even = 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

| 흐름 | 

하나의 while문을 돌며 짝수, 홀수들끼리 노드를 연결한다. 이때 홀수, 짝수를 연결하기 위해 짝수 헤드는 따로 저장해준다.그 다음엔 홀수 노드 마지막을 짝수 헤드로 연결한다. 

 

 

| 핵심 |

#반복하면서 홀짝 처리 
        while even and even.next :
         odd.next, even.next = odd.next.next, even.next.next
            odd, even = odd.next, even.next

 

# 결과