1 month, 1 week

Coding Patterns: In-place Reversal of a Linked List

We will introduce in-place reversal of a linked list pattern, which is very useful to solve the problems involving reversal of a Linked List with the constraint that we need to do it in-place without using extra memory.

Problem: Reverse Linked List                                                                                           

LeetCode 206 - Reverse Linked List [easy]                                       

Given the head of a singly linked list, reverse the list, and return the reversed list.



Input: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
Output: 5 -> 4 -> 3 -> 2 -> 1 -> NULL


class Solution:                                                                  
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        node = head                                                      
        prev = None                                                     
        while node:                                                           
            temp = node.next                                             
            node.next = prev                                                  
            prev = node                                                       
            node = temp                                                        
        return prev                                                                  

Time ComplexityO(N) where N is the number of nodes in the Linked Lists.

Space ComplexityO(1), algorithm runs in constant space.

When the problem gives this constraint and Linked Lists data structure, you should think about in-place reversal of a  linked list pattern.


LeetCode 92 - Reverse Linked List II [medium]                                 

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.

Example:    Input: head = [1,2,3,4,5], left = 2, right = 4

Output: [1,4,3,2,5]                                                                       

Reverse Linked List II Solution:                                                          

class Solution:                                               
    def reverse(self, head, left, right):                               
        curr_node = head                                       
        next_node = curr_node.next                      
        while left < right and next_node:                              
            tmp = next_node.next                                
            next_node.next = curr_node                             
            curr_node = next_node                          
            next_node = tmp                             
            left += 1                                                   
        return head, curr_node, next_node

    def reverseBetween(self, head: [ListNode], left: int, right: int) -> [ListNode]:
        if left == right:                                                         
            return head                                                 
        start = 1                                                
        start_node = head                                             
        prev_start = None                                               
        while start < left and start:                                            
            prev_start = start_node                                             
            start_node = start_node.next                                      
            start += 1                                                                      
        tail, header, tail_next = self.reverse(start_node, left, right)
        if prev_start:                                              
            prev_start.next = header                                      
            head = header                                                  
        tail.next = tail_next                                                  
        return head                                                       


LeetCode 25 - Reverse Nodes in k-Group [hard]                                

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list's nodes, only nodes themselves may be changed.

Example:  Input: head = [1,2,3,4,5], k = 2

Output: [2,1,4,3,5]                                                                                                                                          


class Solution:                                                      
    def reverseLinkedList(self, head, k):                
        new_head, ptr = None, head                       
        while k:                                                        
            next_node = ptr.next                                 
            ptr.next = new_head                                
            new_head = ptr                                       
            ptr = next_node                                      
            k -= 1                                                      
        return new_head                                         
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:      
        ptr = head                                                        
        ktail = None                                                     
        new_head = None                                           
        while ptr:                                                            
            count = 0                                                  
            ptr = head                                                   
            while count < k and ptr:                               
                ptr = ptr.next                                               
                count += 1                                               
            if count == k:                                               
                revHead = self.reverseLinkedList(head, k)
                if not new_head:                                        
                    new_head = revHead                              
                if ktail:                                                        
                    ktail.next = revHead                              
                ktail = head                                               
                head = ptr                                                    
        if ktail:                                                                 
            ktail.next = head                                             
        return new_head if new_head else head