[Top Interview 150] 92. Reverse Linked List II

Solution)

class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        # cur iterates the linked list
        # checkpoint is the node right before the reversal
        cur, checkpoint = head, head

        # Move cur to a node where the reversal starts
        for _ in range(left - 1):
            checkpoint = cur
            cur = cur.next

        # reverse is the head of reversed linked list
        # tail is the tail of the reversed linked list
        reverse, tail = cur, cur
        
        # Reverse the wanted range of nodes
        cur = cur.next
        for _ in range(right - left):
            nextNode = cur.next

            cur.next = reverse
            reverse = cur

            cur = nextNode

        # If the reversal starts at the head
        if left == 1: head = reverse
        else: checkpoint.next = reverse

        tail.next = cur

        return head

 
Problem: LeetCode
 
Time Complexity: O(m)
Space Complexity: O(1)
* m = right
 

Explanation)

In one pass, we have two for-loops.
 
First is to find a node right before the reversal starts. Second is to actually reverse that range of nodes.
Once we reverse the nodes, we'll attach those nodes to the remaining nodes in the linked list that weren't reversed.
 
My solution is kinda messy ths time, so I'll break it into as many steps as possible and try to explain them in full detail. 
 

Initialization)

To iterate the linked list, we'll have a node called cur. Set cur as head.
 
Variable checkpoint will be a node right before the reversal starts. We have this so that whenever we're done with the reversal we can attach those reversed nodes to checkpoint. 
 

def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        cur, checkpoint = head, head

 

Find the checkpoint)

Now, we need to find the node where the reversal starts. Thankfully, we're given a position where it starts, so use that information to find that node.
 
Then our cur would be the node where the reversal starts, and checkpoint will be the node right before cur.
 

def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        cur, checkpoint = head, head

        for _ in range(left - 1):
            checkpoint = cur
            cur = cur.next

 

Reverse)

Now, knowing that our cur is at the start of reversal, it's time to reverse the nodes.
 
Variable reverse will be the head of the reversed nodes. Every for loop, we'll connect a node in reversal order, and reverse will be the head of that reversed nodes.
 
Variable tail will be the tail of the reversed nodes. We have this information so that once the reversal is completed, we can attach the remaining nodes to the tail of reversed nodes.
 
Our logic of reversal is as below.
 
1) Save the next node of cur to nextNode.
- nextNode = cur.next
 
2) Connect the head of reversed nodes to cur. 
- cur.next = reverse
 
3) Now cur is the head of reversed nodes, so we save cur to reverse.
- reverse = cur
 
4) Since we want to continue reversing, set cur as nextNode to keep reversing remaining nodes.
- cur = nextNode
 

def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        cur, checkpoint = head, head

        for _ in range(left - 1):
            checkpoint = cur
            cur = cur.next

        reverse, tail = cur, cur
        cur = cur.next
        for _ in range(right - left):
            nextNode = cur.next

            cur.next = reverse
            reverse = cur

            cur = nextNode

 

Attach the nodes that aren't reversed)

Once the reversal is complete, it's time to attach the remaining nodes to the reversed nodes.
 
1) Attach nodes in front of the reversed nodes
This is the reason why we had checkpoint. If we know a position before the node where the reversal starts, we just need to attach the reversed nodes to that checkpoint.
 
However, if the reversal starts at the head, we have no node to attach. So if the left is 1, then we simply replace head with the reversed nodes.
 
2) Attach nodes after the reversed nodes
This is the reason why we saved tail. Knowing where the reversal ends, we just need to attach the remaining nodes to tail. The remaining nodes are saved in cur.
 

def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        # Initialization

        # Find checkpoint

        reverse, tail = cur, cur
        cur = cur.next
        for _ in range(right - left):
            nextNode = cur.next

            cur.next = reverse
            reverse = cur

            cur = nextNode

        if left == 1: head = reverse
        else: checkpoint.next = reverse

        tail.next = cur

        return head

 
 
 
I gotta admit. The code is messy and kind of hard-coded. But the logic made sense to me so I gave it a try. There's a solution with a similar approach with much cleaner code. Check this solution as well if you don't like mine :(