Topic describes

[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 do not need to retain the initial relative positions of each node in each partition.

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

This problem is not complicated. You only need to classify nodes according to the relationship between node values and x.

The solution is as follows:

  1. Create a virtual head node as the head node of the smaller listsmallHead
  2. Create a virtual head node as the head node of the larger node listbigHead
  3. Iterate through the input linked list to determine whether the node value is less thanx, if the condition is true, the node is connected to the end of the smaller node list, and vice versa
  4. List the larger nodes to the end of the nodenextPoint to thenullTo prevent the appearance of rings
  5. Connect the larger node head to the end of the smaller node list
  6. Return the smaller list head node

The demo is as follows:

Code implementation

Var partition = function(head, x) {const smallHead = new ListNode(0), BigHead = new ListNode(0); // Let smallTail = smallHead, // bigTail = bigHead; If (head.val<x){smalltail.next = head; if(head.val<x){smalltail.next = head; smallTail = smallTail.next; }else{// Connect to the end of the list of larger nodes. bigTail = bigTail.next; } head = head.next; } // Next points to null to prevent loop bigtail.next = null; Smalltail.next = bighead.next; // Smalltail.next = bighead.next; // Smalltail.next = bighead.next; // Smalltail.next = bighead.next; // Return smallHead. Next; };Copy the code

We have now completed leetcode- Interview question 02.04- Split linked lists