Leet Code Reverse Linked List II
Given this basic example, lets look at the general idea in how to reverse a linked list
next = current->next
current->next = prev;
prev = current;
current = next
it sounds reasonable since we iterating once through the singly linked list and those operations are constant time. But, now we have a set where we need to reverse from a left nth position till the right nth position. One common solution to this problem is something like this:
Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.
Constraints:
Basically, the solution above have 3 pointers just like the simple reverse list. it iterates nth times from left -1 to right +1 to be able to reverse the left to right and link the left -1 to right and right + 1 to left.
I asked myself the question whether is a more cleaner way in dealing with this problem.
领英推荐
My solution basically uses a dummy Node that that points to the head as the solution above. We then have a pointer start that points to the dummy node. The current points to the head. We introduce a nthNode counter that starts with 1. That tells the nth node position. We check if the nthNode is less than left. If is less then we set start to current. If is not less then we got our left - 1 position. We then check if current nth node is within the range of >= to left and <= to right. In that range we push the nodes to stack. We then move current to next and update nth position. Current pointer will move till is less or equal to right. When is greater than right we now have our right + 1 position.
We then use our start pointer and iterate the node stack by popping nodes and assigning it to start next pointer. After the stack is empty, we connect start next pointer to current and we return the linked list.
/**
* 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}
*/
var reverseBetween = function (head, left, right) {
if (!head || left === right) {
return head;
}
let dummy = new ListNode(-Infinity, head)
let start = dummy
let current = head
let stack = []
let nthNode = 1
while (current && nthNode <= right) {
if (nthNode < left) {
start = current
}
if (nthNode >= left && nthNode <= right) {
stack.push(current);
}
current = current.next;
nthNode += 1;
}
while (stack.length > 0) {
start.next = stack.pop()
start = start.next
}
start.next = current
return dummy.next
};