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
- 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;
- 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 list
count
; - 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;
- If the list has an odd number, take the last one on the left and remember to cut off the last node in the list
next
Pointing 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.