preface

I thought it was easy at first. Really isTalk is easy， show me your codeWhen submitting leetcode, the code I wrote reported the error as shown in the following figure, which means it formed a loop.I wondered if I didn’t set the next attribute of each node to null before processing each node, causing the loop. The problem is solved.

But when I look at the solution, I’m not dealing with the next property of every node. You only need to process the last node of the list larger than X before splicing.

I. Title Description:

  • 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:
Input: head = [1,4,3,2,5,2], x = 3 output: [1,2,2,4,3,5]Copy the code

Detailed description: see leetcode title description

Ii. Solution:

2.1 thinking:

  • Iterate over the original linked list
  • Split into two linked lists. All nodes in list 1 have values less than x, and all nodes in list 2 have values greater than or equal to x
  • If you join these two lists, the end of list 1 is connected to the head of list 2, can the linked list be looped?
  • Returns the head of list 1

2.2 code

Git code address

2.2.1 Error code: Looped

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @param {number} x * @return {ListNode} */ const partition = function(head, Let small = new ListNode(-1), smallHead = small // Large ListNode values are greater than or equal to x, Let large = new ListNode(-1), largeHead = large While (head) {if(head.val < x) {// Put nodes less than x at the end of the small list, Next = head small = small. Next} else {// Put nodes greater than or equal to x at the end of the large list. Next = head = large. Next} // start the next loop of the original list head = head. Next} // Small joins the large list (note: Next = largehead. next // Return small head. next};Copy the code

2.2.2 Correct code: easy to understand

When traversing the original linked list and dividing it into two linked lists, first disconnect next of the node to be processed and then separate it. It’s just adding two lines of code and changing one line of code to the whiLe loop. Modified pseudocode

While (head) {const next = head.next head. Next = null... Head = head. Next head = next}Copy the code

The complete code

Const partition = function(head, x) {const partition = function(head, x) { Let small = new ListNode(-1), smallHead = small // large ListNode values greater than or equal to x, Let large = new ListNode(-1), largeHead = large While (head) {next const next = head.next head.next = null if(head.val < x) {// Put nodes less than x at the end of small lists, Next = head small = small. Next} else {// Put nodes greater than or equal to x at the end of the large list. Next = head = head. Next head = next} // small join the list Small.next = largeHead. Next // Return smallHead. Next};Copy the code

2.2.3 Correct code: Better details

So let me ask you a question: When does this ring form? The last node of the large list, next, might point to a node in the small list, which would form a loop after concatenation. So we just need to process before concatenation, and add a line of code large. Next = null on the basis of the error code. Code:

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @param {number} x * @return {ListNode} */ const partition = function(head, Let small = new ListNode(-1), smallHead = small // Large ListNode values are greater than or equal to x, Let large = new ListNode(-1), largeHead = large While (head) {if(head.val < x) {// Put nodes less than x at the end of the small list, Next = head small = small. Next} else {// Put nodes greater than or equal to x at the end of the large list. Next = head large = large. Next} // start the next loop of the original list head = head. Next} // Possible loop processing large Small.next = largeHead. Next // Return smallHead. Next}; small.next = smallHead.Copy the code