# Python Program to Reverse Only First N Elements of a Linked List

π‘ Problem Formulation: Given a singly linked list and an integer `n`, the task is to reverse the order of the first `n` elements of the linked list while leaving the rest of the list intact. For instance, if the linked list is `1 -> 2 -> 3 -> 4 -> 5` and `n` is 3, the desired output after the operation would be `3 -> 2 -> 1 -> 4 -> 5`.

## Method 1: Iterative Approach

An iterative approach involves reversing the first `n` nodes of the linked list one at a time. This is performed using a loop that iterates `n` times and reverses the links between the nodes during each iteration.

Here’s an example:

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

prev = None
while n > 0:
next_node = current.next
current.next = prev
prev = current
current = next_node
n -= 1
return prev

# Usage
```

Output of this code snippet:

`3 -> 2 -> 1 -> 4 -> 5`

This code defines a `ListNode` class representing a node in a singly linked list and a function `reverseFirstN` that takes a linked list’s head and an integer `n`. It reverses the first `n` nodes iteratively by adjusting their `next` pointers. After the loop, it connects the reversed portion with the remainder of the list and returns the new head of the linked list.

## Method 2: Recursive Approach

The recursive approach breaks down the problem into smaller instances of the same problem, reversing the first `n` nodes by successively peeling off the head node and recursively calling the function to reverse the rest until `n` reaches zero. Then, it reconnects the reversed section with the remainder of the list.

Here’s an example:

```def reverseFirstNRecursive(head, n, prev=None):
if n == 0 or head is None:
return reverseFirstNRecursive(next_node, n - 1, head)

# Additional code for list construction and function usage is similar to Method 1.
```

Output of this code snippet (using the same example linked list):

`3 -> 2 -> 1 -> 4 -> 5`

Here, we define the function `reverseFirstNRecursive` which takes the current head, the value of `n`, and a `prev` node as arguments. It recursively reverses the first `n` nodes and stops when `n` becomes zero or the list ends. The function returns a tuple with the new head of the reversed section and the first node of the remainder of the list.

## Method 3: Using a Stack

Using a stack exploits the Last-In, First-Out (LIFO) principle to reverse the first `n` elements. Nodes are pushed onto a stack, and then popped and reconnected in reverse order.

Here’s an example:

```def reverseFirstNStack(head, n):
stack = []
while n > 0 and current:
stack.append(current)
current = current.next
n -= 1
while stack:
new_current.next = stack.pop()
new_current = new_current.next
new_current.next = current

# Additional code for list construction and function usage is similar to Method 1.
```

Output of this code snippet (using the same example linked list):

`3 -> 2 -> 1 -> 4 -> 5`

In this method, we define a function `reverseFirstNStack` that takes the head node and an integer `n`. It uses a stack to reverse the order by pushing the nodes onto the stack and then popping them to reconstruct the linked list in reverse order, connecting the rest of the list once done.

## Bonus One-Liner Method 4: Pythonic List Slice Assignment

This method is a more Pythonic solution that operates by copying the linked list into a Python list, reversing the first `n` elements using slice assignment, and then recreating the linked list again from this list.

Here’s an example:

```def reverseFirstNList(head, n):
while current:
lst.append(current)
current = current.next
lst[:n] = lst[:n][::-1]
for i in range(len(lst) - 1):
lst[i].next = lst[i+1]
lst[-1].next = None
return lst[0]

# Additional code for list construction and function usage is similar to Method 1.
```

Output of this code snippet (using the same example linked list):

`3 -> 2 -> 1 -> 4 -> 5`

In this one-liner method, `reverseFirstNList` function converts the linked list into a Python list of nodes, reverses the first `n` elements using slice assignment, and then iterates over the list to fix the `next` pointers, thus recreating the linked list in the desired order.

## Summary/Discussion

• Method 1: Iterative Approach. This method is straightforward and memory-efficient as it utilizes constant space. However, it can be less intuitive than recursive solutions and might be more error-prone due to mutability risks during iteration.
• Method 2: Recursive Approach. Recursive solutions can be more readable but use O(n) stack space, which might lead to stack overflow for large `n` on systems with limited stack size.
• Method 3: Using a Stack. This method clearly models the reversal process but requires O(n) extra space for the stack, which might not be ideal for memory-constrained environments.
• Bonus Method 4: Pythonic List Slice Assignment. This is a concise and readable method, leveraging Python’s slicing capabilities. However, it does not reflect typical linked list operations and loses many of their advantages, such as constant-time insertions and deletions.