# 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](https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/)

### 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:

1. Initialize two pointers, `first` and `second`, both pointing to the head of the linked list.
    
2. <mark>Move the first pointer n steps ahead.</mark>
    
3. Move both pointers one step at a time until the `first` pointer reaches the end of the list.
    
4. At this point, the `second` pointer will be pointing to the nth node from the end.
    

Here's the simplest way to implement it:

```python
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
```

**<mark>Note: </mark>** 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](https://leetcode.com/problems/middle-of-the-linked-list/description/)

### 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:

```python
def find_middle(head: ListNode) -> ListNode:
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow
```

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

## 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`](http://current.next)
        
    * Set [`current.next`](http://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.
        

Perfect and here's the code

```python
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.
        
* **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:

```python
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.