Hello, everyone, I am the beaten Amumu, love algorithm front-end fish old. Recently, I will frequently share with you my thoughts and experiences in the process of brush algorithm. If you also want to improve the forced case of fish old, welcome to pay attention to me, learn together.

The title

143. Rearrange linked lists

Given a head node head of singly linked list L **, singly linked list L can be expressed as:

L0 → L1 →... → Ln minus 1 → LnCopy the code

Please rearrange it to become:

L0 → Ln → L1 → ln-1 → L2 → ln-2 →...Copy the code

You can’t just change the values inside a node, but you need to actually swap nodes.

 

Example 1:

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

Example 2:

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

 

Tip:

  • The length range of the linked list is[1, 5 * 104]
  • 1 <= node.val <= 1000

Train of thought

First of all, if you do not understand how to flip a linked list, you can start from the entry to see [Luffy]_ to the front-end developers of the introduction to the linked list tutorial

  1. If it is a normal array, we can take a double pointer, left one, right one, left one, right one… This problem is too easy haha;
  2. Because it’s a list, we want to get to the last node, so we first have to go through, get the flipped list, and calculate the length of the listcount;
  3. So now we have a positive list and an inverse list, and if we take one of each of them from the positive list and one of each of them from the negative list, we can implement the left one, the right one, the left one, the right one;
  4. If the list has an odd number, take the last one on the left and remember to cut off the last node in the listnextPointing to.

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
 * @return {void} Do not return anything, modify head in-place instead.
 */
var reorderList = function(head) {
    // The next round also needs the head node, find a substitute runner
    let temp = head;

    
    // Calculate the length of the linked list
    let count = 0;
    
    // Generate a list in reverse order
    let reverseHead = null;
    while (temp) {
        let newNode = new ListNode(temp.val);
        newNode.next = reverseHead;
        reverseHead = newNode;
        temp = temp.next;
        count++;
    }

    let result = new ListNode(0);
    let prev = result;

    // Happy take one from the left and one from the right
    while (count > 1) {
        / / the left one
        prev.next = head;
        prev = prev.next;
        head = head.next;

        / / a right
        prev.next = reverseHead;
        prev = prev.next;
        reverseHead = reverseHead.next;

        count -= 2;
    }

    // Only one left in the last round
    if (count === 1) {
        / / the left one
        prev.next = head;
        prev = prev.next;
    }

    prev.next = null;

    return result.next;
};
Copy the code

The results of

The overturned. If we’re out of the output limit, we’re using too much space, so we can start with the reverseHead, because we don’t really use the first part, so we can just flip the second part, or we can start with the result part, so we can just work with the original list instead of creating new memory. We’re going to use the former here.

To optimize the

Use the fast and slow pointer to find the midpoint. Instead of flipping the whole list, cut off the midpoint and flip the last half of the list. Then take a value for each side to operate.

Optimize the 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
 * @return {void} Do not return anything, modify head in-place instead.
 */
var reorderList = function(head) {
    // Find the midpoint by using the fast and slow Pointers
    let fast = head, slow = head;
    let count = 0;
    while (fast) {
        fast = fast.next && fast.next.next;
        slow = slow.next;
        count++;
    }

    // Generate a list in reverse order
    let reverseHead = null;
    while (slow) {
        let newNode = new ListNode(slow.val);
        newNode.next = reverseHead;
        reverseHead = newNode;
        slow = slow.next;
    }

    let result = new ListNode(0);
    let prev = result;

    while (count) {
        / / the left one
        prev.next = head;
        prev = prev.next;
        head = head.next;

        / / a right
        prev.next = reverseHead;
        prev = prev.next;
        reverseHead = reverseHead && reverseHead.next;

        count--;
    }

    return result.next;
};
Copy the code

If you understand it, you can click on it and see you in the next topic. If there is no accident after the article will be in this form, there are good suggestions welcome to comment area.