Reverse Linked List - Python Solution

1. Introduction

Reversing a singly linked list is a fundamental problem in computer science, often used to test understanding of linked list manipulation. This problem involves changing the direction of a linked list so that the last node becomes the first and vice versa. It's a classic example of in-place reversal technique and pointer manipulation.

Problem

Given the head of a singly linked list, the task is to reverse the list and return the head of the reversed list.

2. Solution Steps

1. Initialize three pointers: prev as None, current as the head of the list, and next as None.

2. Traverse the list using the current pointer.

3. For each node in the list:

- Temporarily store the next node.

- Reverse the current.next pointer to point to prev.

- Move prev and current one step forward.

4. Once all nodes are processed, prev will be pointing at the new head of the reversed list.

5. Return prev as the head of the reversed list.

3. Code Program

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

def reverseList(head):
    prev, current = None, head

    while current:
        next = current.next
        current.next = prev
        prev = current
        current = next

    return prev

# Example Usage
# Creating list for demonstration: [1 -> 2 -> 3 -> 4 -> 5]
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
reversed_head = reverseList(head)
# Output the reversed list
output = []
while reversed_head:
    output.append(reversed_head.val)
    reversed_head = reversed_head.next
print(output)

Output:

[5, 4, 3, 2, 1]

Explanation:

1. ListNode Class: The ListNode class represents each node in the linked list.

2. Pointer Initialization: prev starts as None, and current starts at the head of the list.

3. Reversal Logic: The current.next pointer of each node is changed to point to the prev node, effectively reversing the direction of the list.

4. Pointer Movement: prev and current are moved along the list to process each node.

5. End Condition: When current becomes None, prev is at the new head of the list.

6. Result: The function returns the head of the reversed list.

7. In-Place Reversal: The reversal is done in-place without using extra space.