“This is the 8th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021”

The title

Given a list of head nodes and a specific value x, separate the list so that all nodes less than x appear before nodes greater than or equal to x.

You should preserve the initial relative position of each node in the two partitions.

Example 1:

Input: head = [1,4,3,2,5,2], x = 3 output: [1,2,2,4,3,5]Copy the code

LeetCode link: leetcode-cn.com/problems/pa…

Their thinking

  1. At first glance, I want to go through the problem, find the node less than x removed from the original position, add to the front. But they want to keep each node in its original relative position, so you can’t do that.
  2. Create a new list, add the nodes less than x to the new list, join the two sub-lists and return.
  3. Since the ones that are less than x can be added to the new list. The ones that are larger can also be added to the new list, so you don’t have to delete them, and the logic is clearer, but there are more head nodes and node references.
  4. To remove a node from the main list and add it to a new list
    • The last node of the child list points to the new node
    • The traversal pointer moves back
    • The last node of the child list moves back
    • Set next to NULL on the end node of the child list

Code implementation

var partition = function(head, x) { let largeHead = new ListNode(null, null) let smallHead = new ListNode(null, Null) let largeEnd = largeHead // Let samllEnd = smallHead // smallHead, Let curr = head while (curr) {if (curr.val < x) {// when the current node value is less than x //1. Next = curr samllEnd = samllend. next} else {largeend. next = curr largeEnd = Largeend.next} curr = curr.next} // Update next to null for the largest tail node, Samllend. next = largehead. next return smallhead. next}Copy the code

If there are mistakes welcome to point out, welcome to discuss together!