This is the 24th day of my participation in the August Text Challenge.More challenges in August

JavaScript linked list brush problem (2)

Interested in children’s shoes can be rushed, then continue to brush two links list questions ~~

Inversion linked list II (specified position inversion)

92. Reverse linked list II

Give you the head pointer to the singly linked list head and two integers left and right, where left <= right. Reverse the list node from position left to position right to return the reversed list.

Example 1:

Enter: head = [1.2.3.4.5], left = 2, right = 4Output:1.4.3.2.5]
Copy the code

Example 2:

Input: head = [5], left = 1, right = 1 output: [5]Copy the code

Tip:

  • The number of nodes in the linked list is N
  • 1 <= n <= 500
  • -500 <= Node.val <= 500
  • 1 <= left <= right <= n

 

Advancements: Can you use one scan to complete the inversion?

Source: LeetCode link: leetcode-cn.com/problems/re… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Their thinking

Reverse part of the list, and then connect the head and tail to the original broken node.

Code implementation

/** * 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} left
 * @param {number} right
 * @return {ListNode}* /
// Flip the linked list
var reverse = function(head, length) {
    let pre = null;
    let cur = head;
    while(length -- ) {
        let next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    head.next = cur;
    return pre;
}
var reverseBetween = function(head, left, right) {
    // The length of the list to be flipped
    let length = right - left + 1;
    // Set an empty child (new ListNode for.next, null otherwise) at the front of the list.
    // If the left of the flipped list is 1, use pre.next to receive the flipped list without error
    let ret = new ListNode(-1, head)
    let pre = ret;
    let cur = head;
    // Find the node before the flip
    while(-- left) {
        pre = cur;
        cur = cur.next;
    }
    // After flipping the list, point pre.next to the flipped list head
    pre.next = reverse(cur, length);
    return ret.next;
};
Copy the code

Two, a group of K reverse linked list

25. Flip linked lists in groups of K

You are given a linked list, each k nodes in a group of flipped, please return to the flipped list.

K is a positive integer whose value is less than or equal to the length of the list.

If the total number of nodes is not an integer multiple of k, keep the last remaining nodes in the same order.

Advanced:

  • Can you design an algorithm that only uses constant extra space to solve this problem?
  • You can’t just change the values inside the nodes, you need to actually swap nodes.

 

Example 1:

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

Example 2:

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

Example 3:

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

Example 4:

Input: head = [1], k = 1 output: [1]Copy the code

Tip:

  • The number of nodes in the list is in range SZ
  • 1 <= sz <= 5000
  • 0 <= Node.val <= 1000
  • 1 <= k <= sz

Source: LeetCode link: leetcode-cn.com/problems/re… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Their thinking

Determine whether K nodes form a group. If so, reverse K nodes, move the pointer to the last node, and then perform recursive judgment; If not, the entire list is returned.

Code implementation


/** * 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} k
 * @return {ListNode}* /
var reverseKGroup = function(head, k) {
    if(head == null) return null;
    // Create a virtual sentinel node in front of the first node
    let ret = new ListNode(-1, head);
    let pre = ret;
    return reverseRecursion(ret, pre, k)
};
 
var reverseRecursion= function(ret, pre, k) {
    let tail = pre;
    // Determine if there are K nodes that can form a group
    for(var i = 0; i < k; i++) {
        if(tail && tail.next ! =null) {
            tail = tail.next;
        } else {
            tail = null;
            returnret.next; }}// If there are K nodes, invert the K nodes and move the pointer to the last node as the previous node of the next K group, recursively until the remaining nodes cannot form a group
    if(tail ! =null) {
        pre && (pre.next = reverse(pre.next, k));
        for(var i = 0; i < k; i++) {
            pre && (pre = pre.next);
        }
        return reverseRecursion(ret, pre, k)
    }
}
// invert k nodes
var reverse = function(reverseHead, length) {
    let pre = new ListNode(-1, reverseHead);
    let cur = reverseHead;
    while(cur && length--) {
        let next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    reverseHead && (reverseHead.next = cur);
    return pre;
}
Copy the code