[Leetcode/파이썬] 86. Partition List

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:

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

Example 2:

Input: head = [2,1], x = 2
Output: [1,2]

 

Constraints:

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

 

# 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]:
        before_dummy = ListNode(0)
        after_dummy = ListNode(0)

        before = before_dummy
        after = after_dummy

        curr = head

        while curr :
            nxt = curr.next
            curr.next = None

            if curr.val >= x :
                after.next = curr
                after = curr

            else :
                before.next = curr
                before = curr

            curr = nxt

        before.next = after_dummy.next

        return before_dummy.next

 

 

before, after로 나눠서 before에는 x보다 작은 숫자를, after에는 x보다 크거나 같은 숫자를 모아서 before 뒤에 붙이는 식으로 구성하였다. 

1. 각 인접 리스트를 선언하고 난 후, before, after를 왜 다시 선언할까?
2. curr를 순회하면서 before, after 에도 curr를 붙이고 next에도 curr를 붙이는 이유는 뭘까? curr에는 ListNode(val)만 존재함.
3. before_dummy - before, after_dummy - after 간의 관계를 모르겠다. 

next로 끝나는 이유는 가장 앞에 0 이 포함되어 있기 때문에 next로 return .