Technical Interview Question

Given a singly linked list, implement a function to reverse the linked list and return the new head.

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
        
def reverse_linked_list(head):
    # your code here

Example:

Input:

1 -> 2 -> 3 -> 4 -> 5 -> None

Output:

5 -> 4 -> 3 -> 2 -> 1 -> None

Answer

To reverse a singly linked list, we need to swap the next pointers of each node. Let's define two pointers: prev, initially set to None, and curr, initially set to the head of the list. We will iterate through the list, updating these pointers and reversing the next pointers.

def reverse_linked_list(head):
    prev = None
    curr = head

    while curr:
        next_node = curr.next  # store the next node
        curr.next = prev  # reverse the pointer

        prev = curr  # move prev to current node
        curr = next_node  # move curr to next node

    return prev

In each iteration:

1. We store the next node in the next_node variable to avoid losing the reference to the remaining list.
2. We set the next pointer of the current node to the previous node, reversing the pointer.
3. We move the prev pointer to the current node and the curr pointer to the next node.

After the loop, the prev pointer will be pointing to the last node of the original list, which is the new head of the reversed list. We return the prev pointer as the new head.

This solution has a time complexity of O(n) since it visits each node of the linked list once.