Partition List[M,Linked List,Two Pointers]

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

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

그래도 경험치가 좀 늘긴 하나보다..

C의 Medium난이도 문제도 어쨌건 PASS는 시키는 코드를 완성할 줄도 알고 ㅎㅎ

 

1. C

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* partition(struct ListNode* head, int x) {
    if(!head || !head->next) return head;

    struct ListNode dummy1;
    struct ListNode dummy2;
    
    struct ListNode* small = &dummy1;
    struct ListNode* big = &dummy2;
    struct ListNode* curr = head;

    while(curr){
        if(curr->val < x){
            small->next = curr;
            small = small->next;
        }else{
            big->next = curr;
            big = big->next;
        }
        curr = curr->next;
    }
    big->next = NULL;
    small->next = dummy2.next;
    return dummy1.next;
}

 

좀 더 효과적인 방법이 있으려나?

 

잘 없다. 아래 C++코드 정도? 근데 performance는 비슷하다.

 

2. 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 || !head->next) return head;
        ListNode small;
        ListNode big;
        vector<ListNode*> vec = {&small,&big};
        while(head){
            if(head->val < x){
                vec[0]->next = head;
                vec[0] = vec[0]->next;
            }else{
                vec[1]->next = head;
                vec[1] = vec[1]->next;
            }
            head = head->next;
        }
        vec[1]->next = nullptr;
        vec[0]->next = big.next;

        return small.next;
    }
};

 

3. Python

C / C++로 할 수 있는 거면 Python으론 무조건 할 수 있다고 보면 된다 ㅋ;

# 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]:
        small = ListNode(999,None)
        big = ListNode(1004,None)
        s = small
        b = big
        while head :
            if head.val < x :
                s.next = head
                s = s.next
            else:
                b.next = head
                b = b.next
            head = head.next
        b.next = None
        s.next = big.next

        return small.next