Reverse a linked list from position m to n. Do it in one-pass.
Note: 1 ≤ m ≤ n ≤ length of list.
Example:
Input: 1->2->3->4->5->NULL, m = 2, n = 4 Output: 1->4->3->2->5->NULL
The description was taken from https://leetcode.com/problems/reverse-linked-list-ii/.
#O(N) Time, O(1) Spaceclass Solution: def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode: if not head: return None prev, curr = None, head while m > 1: prev = curr curr = curr.next m -= 1 n-= 1 pre_subhead, subtail = prev, curr while n: next_node = curr.next curr.next = prev prev = curr curr = next_node n -= 1 if pre_subhead: pre_subhead.next = prev else: head = prev subtail.next = curr return headIn-place swaps or reversals of linked lists will typically come down to a few tasks:
Saving a reference to the node of the next iteration
Redirecting .next pointers
Iterating to the previously saved node references
Using these steps, we can solve this problem by traversing the list with a counter until we get to the beginning of the sublist we would like to reverse.
After that, we will reverse each node of the sublist n times.
When our reversal is done, we will reconnect the sublist head and tail back to the rest of the list.
If the head is null, then we can't reverse anything.
if not head: return None
Let's create our first two pointers, then initialize them at null and the head, respectively.
Our prev will be used to track the previous node, curr will be used to track the current node.
prev, curr = None, head
We can then use a loop to keep moving our pointers down the list until m is one. When that happens we're in position to start the reversal.
while m > 1: prev = curr curr = curr.next m -= 1 n-= 1
Once we are in position, we are going to want to keep track of the nodes that are connected to the sublist we are about to reverse.
The pre_subhead pointer will keep track of the node that comes before the sublist head and the subtail pointer will keep track of the current node curr is at. The reason curr will be the sublist tail is that once we reverse the sublist, the first node of the sublist will be thrown all the way to the right and will need to connect back to the remainder of the input list.
pre_subhead, subtail = prev, curr
While n is greater than zero, we still have nodes to reverse.
while n:
At the beginning of each iteration, we will save the next node.
next_node = curr.next
We want to do this because once we overwrite curr.next and set it to the previous node, we will lose our bridge to get to the next node. The third pointer is just a placeholder.
Once we set the third pointer, we will overwrite the reference to our next node by setting it to the previous node, prev.
curr.next = prev
We will then move both our current node pointer, curr and our previous node pointer, prev forward.
We will also decrement n to signify that this current node has been reversed.
prev = curr curr = next_node n -= 1
If the pre_subhead node was not a null value, meaning that we didn't start the reversal from the very first node of the input list with m initially being one, then we will connect the pre_subhead node to prev. Prior to reversing the list, this was the node on the far right of the sublist, making it the head of the reversed sublist.
if pre_subhead: pre_subhead.next = prev
If we did start the reversal from the very first node of the input list, then the head of the output list would be prev for the same reason just mentioned.
else: head = prev
Now we just need to connect the sublist tail to the remainder of the list which would be where curr last ventured to.
The reason for this is that the loop broke when n became zero and curr went out of bounds of the sublist, either moving to a node of the remaining list or a null value.
subtail.next = curr
Once we're done, we will return the head of the reordered linked list.
return head