LeetCode 86(Partition List, Python)

1. 문제 링크

• https://leetcode.com/problems/partition-list/

Partition List - LeetCode

2. 문제 설명

• 연결 리스트 head = [1,4,3,2,5,2]와 기준 값 x = 3이 주어지면
• 3보다 작은 1, 2, 2는 앞쪽으로, 나머지는 뒤쪽으로 보내어 연결 리스트 [1, 2, 2, 4, 3, 5]를 반환하는 문제
• 이때 3 앞에 오는 1, 2, 2 끼리의 순서, 뒤에 오는 4, 3, 5의 순서는 처음 그대로 유지.
• 그러니까 [1, 2, 2, 3, 4, 5]는 안됨.

3. 처음 풀이

• 연결 리스트 헤드 left, right를 만들어 준다.
• 주어진 연결 리스트의 노드를 순회하며 그 값이 x 보다 작으면 left 노드의 뒤에, x보다 크거나 같으면 right의 노드의 뒤에 연결을 해준다.
• 마지막으로 left 노드의 뒤에 right.next를 연결해주고 left.next를 반환하면 된다.
• 이때 사이클이 생성되지 않도록 right의 마지막 노드의 next는 None 처리.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        # 작은 값들을 담을 왼쪽 연결 리스트와 크거나 같은 값들을 담을 오른쪽 연결 리스트 생성
        left = ListNode(0)
        right = ListNode(0)
        
        # 현재 노드를 가리킬 포인터
        cur_left = left
        cur_right = right
        
        # 입력으로 주어진 연결 리스트를 순회
        node = head
        while node:
            # 현재 노드의 값이 기준값 x보다 작으면 왼쪽 연결 리스트에 추가
            if node.val < x:
                cur_left.next = node
                cur_left = cur_left.next
            # 그렇지 않으면 오른쪽 연결 리스트에 추가
            else:
                cur_right.next = node
                cur_right = cur_right.next
                
            # 다음 노드로 이동
            node = node.next
        
        # 왼쪽 연결 리스트의 끝에 오른쪽 연결 리스트를 이어붙이기
        cur_left.next = right.next
        # 오른쪽 연결 리스트의 끝(안하면 사이클 생길 수 있음)
        cur_right.next = None
        
        # 완성된 연결 리스트를 반환
        return left.next

4. 다른 풀이

• 이 문제는 다양한 풀이를 살펴보았지만 핵심 로직이 모두 같았다. 

5. 배운 점

• 오랜만에 다시 연결 리스트 문제들이 등장하고 있다. 익숙해지기!