algoadvance

Reverse a singly linked list.

Example:

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

Clarifying Questions

1. What is the structure of the linked list node? Each node will have two fields: val (the value) and next (the pointer to the next node).

2. Are there any constraints on the values of the linked list’s nodes? No specific constraints other than typical integer values.

3. Do we need to handle any specific edge cases?

   • An empty linked list (i.e., head is None).
   • A linked list with only one node.

Strategy

1. We’ll use an iterative approach to reverse the linked list, although a recursive approach is also possible.
2. The plan:
   • Initialize two pointers, prev as None and curr as the head of the list.
   • Traverse the list. For each node:
     • Store the next node temporarily.
     • Reverse the current node’s next pointer to point to prev.
     • Move prev and curr one step forward.
3. The prev pointer will eventually point to the new head of the reversed list.

Code

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseList(head: ListNode) -> ListNode:
    prev = None
    curr = head
    
    while curr:
        next_temp = curr.next  # Store the next node
        curr.next = prev       # Reverse the link
        prev = curr            # Move prev to current node
        curr = next_temp       # Move curr to next node
    
    return prev

# Helper function to print the list (for understanding/debugging purposes)
def printList(head: ListNode):
    while head:
        print(head.val, end=" -> ")
        head = head.next
    print("NULL")

Time Complexity

• Time Complexity: O(n) where n is the number of nodes in the linked list. We visit each node once.
• Space Complexity: O(1) because we are reusing the existing node structures and only using a few pointers.

This approach ensures that the linked list is reversed efficiently with minimal memory overhead.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?