Record an algorithm problem

Separated list

86. Separated Linked Lists – Force Links (LeetCode) (leetcode-cn.com)

Requirements:

* Nodes less than x are placed on the left, and nodes greater than or equal to x are placed on the right. * Keep the original position relative to each otherCopy the code

The linked list should be traversed at least once. The problem is how to handle node connections. The concept of a pseudo-node is mentioned here. You can create a new node to start with, and you can initialize the initial node without doing an if judgment.

You don’t really have to worry about old connections between nodes because they reset as nodes are assigned. You just need to join the edges of the two areas after partition

    function partition(head, x) {
        const before = new ListNode()
        const after = new ListNode()
    
        / / pointer
        let minStart = before
        let maxStart = after

        / / traverse
        while(head) {
            if (head.val < x) {
                minStart = minStart.next = head
            } else {
                maxStart = maxStart.next = head
            }

            head = head.next
        }
        
        // When there is no node less than x or greater than or equal to x, start with another node
        if (before.next == null) {
            head = after.next
        } else {
            head = before.next
        }

        // Connect end to end, and clear tail
        // It is worth noting that minStart assignment does not matter if there are no nodes less than x
        minStart.next = after.next
        maxStart.next = null

        return head
    };
Copy the code