솔루션: 파티션 목록

이것은 일련의 Leetcode 솔루션 설명( )의 일부입니다. 이 솔루션이 마음에 들었거나 유용하다고 생각되면 이 게시물에 좋아요를 누르거나 찬성 투표my solution post on Leetcode's forums를 해주세요.

Leetcode 문제 #86(중간): 파티션 목록

설명:

(다음으로 이동: Solution Idea || 코드: JavaScript | Python | Java | C++ )

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]
Visual:

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

제약:

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

아이디어:

(다음으로 이동: Problem Description || 코드: JavaScript | Python | Java | C++ )

여기에서 가장 쉬운 일은 반환하려는 목록의 앞 부분과 뒷 부분에 대해 별도의 연결 목록을 만드는 것입니다. 이를 달성하기 위해 먼저 더미 헤드(fdum, bdum)를 생성한 다음 전면, 후면 및 메인 목록(front, back, curr) 각각의 현재 노드에 대한 포인터를 생성해야 합니다.

그런 다음 기본 목록을 반복하고 노드의 값에 따라 각 노드를 앞뒤로 함께 연결할 수 있습니다.

끝에 도달하면 두 개의 하위 목록을 함께 꿰매고 뒤 끝을 막은 다음 더미 머리를 뺀 새 목록을 반환하면 됩니다.

구현:

네 가지 언어 모두의 코드 간에는 약간의 차이만 있습니다.

자바스크립트 코드:

(다음으로 이동: Problem Description || Solution Idea )

var partition = function(head, x) {
    let fdum = new ListNode(0), bdum = new ListNode(0),
        front = fdum, back = bdum, curr = head
    while (curr) {
        if (curr.val < x)front.next = curr, front = curr
        else back.next = curr, back = curr
        curr = curr.next
    }
    front.next = bdum.next, back.next = null
    return fdum.next
};

파이썬 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        fdum, bdum = ListNode(0), ListNode(0)
        front, back, curr = fdum, bdum, head
        while curr:
            if curr.val < x:
                front.next = curr
                front = curr
            else:
                back.next = curr
                back = curr
            curr = curr.next
        front.next, back.next = bdum.next, None
        return fdum.next

자바 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode fdum = new ListNode(0), bdum = new ListNode(0),
                 front = fdum, back = bdum, curr = head;
        while (curr != null) {
            if (curr.val < x) {
                front.next = curr;
                front = curr;
            } else {
                back.next = curr;
                back = curr;
            }
            curr = curr.next;
        }
        front.next = bdum.next;
        back.next = null;
        return fdum.next;
    }
}

C++ 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode *fdum = new ListNode(0), *bdum = new ListNode(0),
                 *front = fdum, *back = bdum, *curr = head;
        while (curr) {
            if (curr->val < x) front->next = curr, front = curr;
            else back->next = curr, back = curr;
            curr = curr->next;
        }
        front->next = bdum->next, back->next = nullptr;
        return fdum->next;
    }
};