Løsning:Partitionsliste

Dette er en del af en række Leetcode-løsningsforklaringer (indeks). Hvis du kunne lide denne løsning eller fandt den nyttig, synes godt om dette indlæg og/eller stem op mit løsningsindlæg på Leetcodes fora.

Leetcode-problem #86 (Medium ):Partitionsliste

Beskrivelse:

(Hop til :Løsningsidé || Kode :JavaScript | Python | Java | C++ )

Eksempler:

Begrænsninger:

Idé:

(Hop til :Problembeskrivelse || Kode :JavaScript | Python | Java | C++ )

Den nemmeste ting at gøre her er at oprette separate linkede lister for de forreste og bagerste dele af listen, vi ønsker at returnere. For at opnå det, bør vi først oprette nogle dummy-hoveder (fdum, bdum ), opret derefter pointere for de aktuelle noder hver af for-, bag- og hovedlisterne (front, back, curr ).

Så kan vi blot iterere gennem hovedlisten og sy hver node sammen til enten front eller tilbage , afhængigt af nodens værdi.

Når vi når slutningen, mangler vi bare at sy de to underlister sammen, og sørg for at lukke enden af ​​tilbage , og derefter retur vores nye liste, minus dummy-hovedet.

Implementering:

Der er kun mindre forskelle mellem koden for alle fire sprog.

Javascript-kode:

(Hop til :Problembeskrivelse || Løsningsidé )

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
};

Python-kode:

(Hop til :Problembeskrivelse || Løsningsidé )

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

Java-kode:

(Hop til :Problembeskrivelse || Løsningsidé )

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++-kode:

(Hop til :Problembeskrivelse || Løsningsidé )

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;
    }
};