“This is the 24th day of my participation in the November Gwen Challenge. See details of the event: The Last Gwen Challenge 2021”.

The title

Link: leetcode-cn.com/problems/pa…

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 =,4,3,2,5,2 [1], x = 3 output:,2,2,4,3,5 [1]

Example 2:

** input: **head = [2,1], x = 2

 

Tip:

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

Their thinking

Idea 1

  • It is important to understand the reference relationship between Pointers and lists
  • After referring to daishen’s code, there is a question that this is only the next node that changes the pointer, why is the linked list also changed
  • SmallPoint. Next = cur //smallPoint = before. Next = cur
  • SmallPoint = smallPoint. Next // The pointer of smallPoint is changed to before next, and before Next and smallPoint point are the same object.

code

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @param {number} x
 * @return {ListNode}* /
var partition = function (head, x) {
    const listNode = new ListNode(0)
    listNode.next = head
    let before = new ListNode(0)
    let after = new ListNode(0)
    let smallPoint = before
    let bigPoint = after
    let cur = listNode.next
    while (cur) {
        if (cur.val >= x) {
            bigPoint.next = cur
            bigPoint = bigPoint.next
        } else {
            smallPoint.next = cur
            smallPoint = smallPoint.next
        }
        cur = cur.next
    }
    bigPoint.next = null
    smallPoint.next = after.next
    return before.next
};
Copy the code

Idea 2

The first thing that comes to mind is to use space to classify anything greater than x as a chain and anything less than x as a chain. And then I’m going to attach the big list to the little list. Get things done. So just walk through the list, copy the nodes, manipulate the links. Snap, quick.

Time complexity

O(n)

Spatial complexity

O(n)

code

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @param {number} x
 * @return {ListNode}* /
var partition = function(head, x) {
    let ltX = {next: null}, gtX = {next: null};
    let lastltX = ltX, lastgtY = gtX;
    while (head) {
        let node = new ListNode(head.val);
        if (head.val < x) {
            lastltX.next = node;
            lastltX = node;
        } else {
            lastgtY.next = node;
            lastgtY = node;
        }
        head = head.next;
    }
    lastltX.next = gtX.next;
    return ltX.next;
};
Copy the code

Idea 3

  1. If the header does not return null directly
  2. Define the size of two nodes
  3. Define size two Pointers
  4. The for loop compares, if the value is smaller than the specified value in the small list, and the value is larger in the large list
  5. Stitching list

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}* /
var partition = function(head, x) {
    if(! head){return null};
    let big= new ListNode(), small = new ListNode();
    let bigNode = big, smallNode = small;
    for(letcur=head,next; cur; cur=next){ next = cur.next; cur.next =null;
        if(cur.val < x){
            smallNode.next = cur;
            smallNode=cur;
        }else{
            bigNode.next = cur;
            bigNode = cur;
        }
    }
    smallNode.next = big.next;
    return small.next

};
Copy the code