[LeetCode] 86 | Partition List | Python

---

문제 링크: https://leetcode.com/problems/partition-list/

---

문제

Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

 

Example 1:

---

조건

• The number of nodes in the list is in the range [0, 200].
• -100 <= Node.val <= 100
• -200 <= x <= 200

---

내 풀이

x보다 작은 값들을 모을 smaller 리스트, 그렇지 않은 값들을 모을 bigger 리스트를 모은다.

나중에 smaller를 리턴해야하는데, smaller.next로 가면 smaller의 시작점을 찾기 어려우므로 이를 대신할 s=smaller를 이용한다.

List를 앞에서부터 차례로 보며 그 크기가 x보다 작으면 smaller에 추가하고, 그렇지 않으면 bigger에 추가한다.

smaller 뒤에 bigger를 붙이고 리턴한다.

bigger.next를 붙이는 이유는 처음에 bigger를 만들 때 dummy value인 0으로 만들었고, 그 뒤의 값부터 유효하기 때문이다.

이와 같은 이유도 리턴할 때 smaller.next를 리턴한다.

---

코드

# 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]:
        if not head:    return head
        
        smaller, bigger = ListNode(0), ListNode(0)
        s, b = smaller, bigger
        
        if head.val < x:
            s.next = ListNode(head.val)
            s = s.next
        else:
            b.next = ListNode(head.val)
            b = b.next
        
        while head.next:
            head = head.next
            if head.val < x:
                s.next = ListNode(head.val)
                s = s.next
            else:
                b.next = ListNode(head.val)
                b = b.next
        
        s.next = bigger.next
        return smaller.next