# LinkedList Interview patterns Part 1

LinkedLists are one of the most common interview topics that we see in interviews.

## nth Place from End

This is one of most common interview questions that we've seen in the past from companies like Adobe, AWS, Amazon.

You can find this question pretty much any code practice site like Leetcode, Hackerrank or any other site.

For instance here's a slight variation of the problem on Leetcode: Problem

### Strategy:

To find the nth node from the end of a linked list in Python using O(1) space, you can use the two-pointer technique. Here's a step-by-step explanation and implementation:

Initialize two pointers,

`first`

and`second`

, both pointing to the head of the linked list.Move the first pointer n steps ahead.

Move both pointers one step at a time until the

`first`

pointer reaches the end of the list.At this point, the

`second`

pointer will be pointing to the nth node from the end.

Here's the simplest way to implement it:

```
class ListNode:
def __init__(self, value=0, next=None):
self.value = value
self.next = next
def find_nth_from_end(head: ListNode, n: int) -> ListNode:
first = head
second = head
# Move the first pointer n steps ahead
for _ in range(n):
# If our list is smaller than the n. Return None
if first is None:
return None # Out of Bounds
first = first.next
# Move both pointers until the first pointer reaches the end
while first:
first = first.next
second = second.next
return second
```

**Note: ** There is another way to implement it using Arrays but it'll take up Space Complexity of O(n), which generally is constrained in lot of big interviews.

## Find middle of a LinkedList:

This is another common recurring question in LinkedList interviews.

Here's the question on Leetcode: Middle of List

### Strategy:

To find the middle of a linked list in Python using O(1) space complexity, you can use the "tortoise and hare" algorithm.

This algorithm involves using two pointers:

a slow pointer that moves one step at a time

a fast pointer that moves two steps at a time.

When the fast pointer reaches the end of the list, the slow pointer will be at the middle.

Here's the easiest implementation:

```
def find_middle(head: ListNode) -> ListNode:
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
```

This algorithm ensures that the space complexity is O(1) since only a constant amount of extra space is used.

## Reverse a LinkedList:

Another common question we get asked is to reverse an existing LinkedList using either recursion or using regular way. So in this tutorial we'll cover both:

### Iterative Strategy:

**Initialize Three Pointers**:`prev`

to`None`

`current`

to the head of the list`next`

to`None`

(will be used to store the next node)

**Iterate Through the List**:Update

`next`

to`current.next`

Set

`current.next`

to`prev`

(this reverses the link)Move

`prev`

to`current`

Move

`current`

to`next`

**Set the New Head**:- After the loop,
`prev`

will be the new head of the reversed list.

- After the loop,

Perfect and here's the code

```
def reverse_list(head: ListNode):
prev = None
current = head
while current:
next = current.next
current.next = prev
prev = current
current = current.next
# This is the head
return prev
```

### Recursion Strategy:

**Base Case**:- If the node is
`None`

or the next node is`None`

, return the node.

- If the node is
**Recursive Step**:Reverse the rest of the list from the second node.

Set the next node’s next pointer to the current node.

Set the current node’s next pointer to

`None`

.

**Return the New Head**:- The new head will be returned from the base case

Perfect and here's the code:

```
def reverse_list_recursion(head):
if head is None or head.next is None:
return head
rest = reverse_list_recursion(head.next)
head.next.next = head
head.next = None
return rest
```

These are but some of the concepts we need in LinkedLists. In the remaining series we'll cover easy patterns for:

Detect a Cycle in a Linked List

Merge two sorted Linked Lists

Check if a LinkedList is Palindrome

Remove duplicates from a sorted LinkedList

Intersection of two LinkedLists

Flatten a multilevel doubly LinkedList

Partion List

Rotate List

Add two numbers represented by linked lists

While the code would be important we'll also go through identify common patterns so that we can hack away at any questions the interviewer throws at us.

I hope to hear more from you guys in the Journey and good luck with you #DSA preparations.