[LeetCode] 86. Partition List

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

Partition List - LeetCode

문제 유형 : 연결 리스트

문제 난이도 : Medium

 

문제

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.

 

연결 리스트가 있습니다. x보다 작은 수를 가진 노드를 앞으로, x보다 크거나 같은 수를 가진 노드를 뒤로 나누시오.

단, 두 파티션 내에서 기존의 순서 규칙이 지켜져야 합니다.

 

풀이

x보다 작으면 before 연결리스트에, 크거나 같으면 after 연결리스트에 추가해준 뒤, before 다음에 after를 연결시켜준다.

 

코드

C++

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode before_head(0);
        ListNode* before = &before_head;

        ListNode after_head(0);
        ListNode* after = &after_head;

        while(head) {
            if(head -> val < x) {
                before -> next = head;
                before = before -> next;
            } else {
                after -> next = head;
                after = after -> next;
            }

            head = head -> next;
        }
        after -> next = nullptr;
        before -> next = after_head.next;

        return before_head.next;
    }
};

 

Python3

class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        before_head = ListNode(0)
        before = before_head

        after_head = ListNode(0)
        after = after_head

        while head:
            if head.val < x:
                before.next = head
                before = before.next
            else:
                after.next = head
                after = after.next
            head = head.next

        after.next = None
        before.next = after_head.next

        return before_head.next

 

Dart

class Solution {
  ListNode? partition(ListNode? head, int x) {
    ListNode before_head = ListNode(0);
    ListNode? before = before_head;

    ListNode after_head = ListNode(0);
    ListNode? after = after_head;

    while(head != null) {
        if(head.val < x) {
            before!.next = head;
            before = before.next;
        } else {
            after!.next = head;
            after = after.next;
        }

        head = head.next;
    }

    after!.next = null;
    before!.next = after_head.next;

    return before_head.next;
  }
}

 

Java

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode before_head = new ListNode(0);
        ListNode before = before_head;

        ListNode after_head = new ListNode(0);
        ListNode after = after_head;

        while (head != null) {
            if (head.val < x) {
                before.next = head;
                before = before.next;
            } else {
                after.next = head;
                after = after.next;
            }
            head = head.next;
        }

        after.next = null;
        before.next = after_head.next;

        return before_head.next;
    }
}

 

Swift

class Solution {
    func partition(_ head: ListNode?, _ x: Int) -> ListNode? {
        let before_head = ListNode(0)
        var before = before_head

        let after_head = ListNode(0)
        var after = after_head

        var current = head
        while current != nil {
            if current!.val < x {
                before.next = current
                before = before.next!
            } else {
                after.next = current
                after = after.next!
            }
            current = current!.next
        }

        after.next = nil
        before.next = after_head.next

        return before_head.next
    }
}