Reverse Linked List easy

Problem Statement

Reverse a singly linked list.

Example 1:

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

Example 2:

Input: 1->NULL
Output: 1->NULL

Steps

To reverse a linked list iteratively, we'll follow these steps:

1. Initialization: We'll need three pointers:

   • prev: Initially None, it will point to the previously reversed node.
   • curr: Initially points to the head of the list.
   • next: A temporary pointer to store the next node in the original list.

2. Iteration: We'll iterate through the list, reversing the links at each step. In each iteration:

   • We store the curr.next in next to save it for the next iteration.
   • We change curr.next to point to prev. This reverses the link.
   • We move prev one step forward to curr.
   • We move curr one step forward to next.

3. Termination: The loop terminates when curr reaches None, which means we've reached the end of the original list. At this point, prev points to the new head of the reversed list.

Explanation

The algorithm works by iteratively detaching a node from the original list and attaching it to the beginning of the reversed list. The prev, curr, and next pointers allow us to manage the links effectively without losing track of the nodes.

Code

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

def reverseList(head):
    prev = None
    curr = head
    while curr:
        next = curr.next  # Store the next node
        curr.next = prev  # Reverse the link
        prev = curr       # Move prev forward
        curr = next       # Move curr forward
    return prev

# Example usage:
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
reversed_head = reverseList(head)

#Print the reversed linked list
while reversed_head:
    print(reversed_head.val, end="->")
    reversed_head = reversed_head.next
print("NULL")

head = ListNode(1)
reversed_head = reverseList(head)
while reversed_head:
    print(reversed_head.val, end="->")
    reversed_head = reversed_head.next
print("NULL")

Complexity

• Time Complexity: O(N), where N is the number of nodes in the linked list. We iterate through the list once.
• Space Complexity: O(1). We use a constant amount of extra space for the pointers (prev, curr, next).