Leetcode 518. 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.

연결 리스트의 head와 정수 x가 주어진다.
x보다 작은 값은 연결리스트의 왼쪽에, x보다 크거나 같은 값은 오른쪽에 가도록 해라
단, 값의 위치가 바뀔때 상대적인 위치는 유지되어야 한다.

예시

Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]
Explanation: 1, 2, 2 는 3보다 작고 | 4, 3, 5는 3보다 크거나 같다. 상대적 위치는 유지 
( 3이 원래 4보다 뒤에 있기에 옮겨진 이후에도 이를 유지한다. )

제한

• 연결 리스트의 길이는 0 ~ 200 이다.
• $-100 <= x <= 200$
• $-200 <= x <= 200$

풀이

2개의 리스트를 두어 하나는 x보다 작은 값이, 하나는 x보다 크거나 같은 값이 되도록 추가 한 후 이 둘을 연결해 리턴한다.

class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        numbers: List[int] = []
        
        # 왼쪽, 오른쪽 연결리스트
        left_header = ListNode()
        right_header = ListNode()
        
        # 차후 리턴 or 연결할 부분을 미리 정의
        return_header = left_header
        connect_header = right_header
        
        # 옮기기
        while head != None:
            if(head.val < x):
                left_header.next = ListNode(head.val)
                left_header = left_header.next
            else:
                right_header.next = ListNode(head.val)
                right_header = right_header.next
            head = head.next
        
        # 연결
        left_header.next = connect_header.next
                
        return return_header.next