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

[B] [C] [D]

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

Example 2:

Input: head = [2,1], x = 2Copy the code

Tip:

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

In this case, we need to split the linked list into two partitions according to the given values, and the relative positions of the nodes in the partition should remain the previous relative positions

First of all, when the given linked list is empty or has only one node, it cannot be separated and can be directly returned to the original linked list

If the number of input linked list nodes is greater than 1, the nodes in the input linked list need to be partitioned according to the given value X

Finally, join the list of partitioned nodes with storage greater than or equal to X to the following list with storage less than x

Finally return the linked list of results

The solution is as follows:

  1. If the linked list is empty or has only one node, return the original list directly
  2. createsmallHeadThe storage value of the virtual head node is less thanxIs a linked list of nodes
  3. createbigHeadThe virtual head node stores a value greater than or equal toxIs a linked list of nodes
  4. Iterate over both sides of the input to determine if the value of the current node is less thanxIf yes, the node is connected tosmallHeadThe end of the list, and vice versabigHeadThe end of the list
  5. willbigHeadOf the node at the end of the listnextPointer tonullTo prevent the result list from becoming a loop
  6. willbigHeadLinked list joins tosmallHeadThe end of the list
  7. returnsmallHead.nextCan be

The overall process is as follows:

The code is as follows:

Var partition = function (head, x) {/ /, sentenced to list is empty or only one node, direct return the if (head = = = null | | head. The next = = = null) return the head; Const smallHead = new ListNode(0), const smallHead = new ListNode(0), const smallHead = new ListNode(0); let smallTail = smallHead, bigTail = bigHead, cur = head; // If (cur.val< X){smalltail.next = cur; // If (cur.val< X){smalltail.next = cur; smallTail = smallTail.next; }else{// Connect to the end of the larger list. bigTail = bigTail.next; } cur = cur.next; } // Set next to null to prevent the resulting list from being looped. Next = null; Smalltail.next = bighead.next; smalltail.next = bighead.next; // Next return smallhead.next; };Copy the code

At this point we are done with leetcode-86-separated linked lists

If you have any questions or suggestions, please leave a comment!