Can you script a program that inverses the order of a linked list?

Question Analysis

The question asks you to script a program that reverses a linked list. This is a common coding problem that tests your understanding of linked list data structures and your ability to manipulate pointers.

• Linked List: A linear data structure where elements are not stored at contiguous memory locations. Each element (node) contains a data part and a reference (or pointer) to the next node in the sequence.
• Reverse a Linked List: To reverse a linked list means to change the direction of the pointers in such a way that the head of the list becomes the tail and vice versa.

The task is to implement a function that takes the head of a linked list and returns the head of the reversed list.

Answer

Below is a Python implementation to reverse a singly linked list. This implementation iteratively updates the pointers of the list.

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

def reverse_linked_list(head):
    prev = None
    current = head
    
    while current is not None:
        next_node = current.next  # Store the next node
        current.next = prev       # Reverse the current node's pointer
        prev = current            # Move prev and current one step forward
        current = next_node
    
    return prev  # prev will become the new head of the reversed list

# Example Usage:
# Creating a linked list 1 -> 2 -> 3 -> None
head = ListNode(1, ListNode(2, ListNode(3)))

# Reversing the linked list
reversed_head = reverse_linked_list(head)
# The linked list is now 3 -> 2 -> 1 -> None

Explanation:

• Initialization: Start with two pointers, prev (initialized to None) and current (initialized to head).
• Iterative Process: Traverse the list while updating pointers:
  • Save the next node in a temporary variable next_node.
  • Reverse the current node's pointer to point to the previous node (prev).
  • Move prev and current one step forward.
• Result: Once the loop completes, prev is the new head of the reversed list. Return prev.

This solution iteratively reverses the linked list in O(n) time complexity, where n is the number of nodes, and it uses O(1) additional space.