CA 22 - Reverse a Linked List

Problem
Reverse a Linked List
You are given the head of a singly linked list.
Your task is to reverse the linked list and return the new head.

Example
Input: 1 → 2 → 3 → 4
Output: 4 → 3 → 2 → 1

Approach

We reverse the linked list by changing the direction of the next pointers.

Steps:

• Initialize three pointers:
• prev = None
• curr = head
• Traverse the list:
• Store the next node
• Reverse the link (curr.next = prev)
• Move prev and curr forward
• At the end, prev will be the new head

This effectively flips the list in one pass.

** Complexity:**
Time Complexity: O(n)
Space Complexity: O(1)

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_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return pre
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
reversed_head = reverseList(head)
curr = reversed_head
while curr:
    print(curr.val, end=" -> " if curr.next else "")
    curr = curr.next