86. Partition List

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

Partition List - LeetCode

 

node 목록의 header와 임의의 정수가 주어졌을 때, 임의의 정수보다 작은 val를 가진 node는 임의의 정수 node보다 left에 존재하도록 목록을 변경해 반환하는 문제다.

 

리스트를 순회하며 임의의 정수보다 작은 node면 앞단 목록(front)에, 크면 뒷단 목록(back)에 연결을 추가하고, 순회가 끝나면 두 목록을 연결해 최종 목록을 반환한다.

 

[C++]

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        if (!head) {
            return head;
        }
        
        ListNode ftemp(0);
        ListNode btemp(0);
        
        ListNode* curr = head;
        ListNode* front = &ftemp; // front of pivot
        ListNode* back = &btemp; // back of pivot
        
        while (curr)
        {
            if (curr->val < x)
            {
                front->next = curr;
                front = curr;
            }
            else
            {
                back->next = curr;
                back = curr;
            }
            
            curr = curr->next;
        }
        
        front->next = btemp.next;
        back->next = nullptr;
        
        return ftemp.next;
    }
};

 

 

[Python3]

# 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]:
        front = h1 = ListNode(0)
        back = h2 = ListNode(0)

        while head:
            if head.val < x:
                front.next = head
                front = head
            else:
                back.next = head
                back = head
            
            head = head.next
        
        front.next = h2.next
        back.next = None
        
        return h1.next