Welcome to this week’s Interview Questions in Python! I hope last week you learned all you could and that it leveled up your skills! This week, we’re going to be focusing on singly-linked lists, one of the most important data structures in all of Computer Science. Linked lists are used in the implementation of stacks, queues, graphs, and more.

## Linked List Code

Before we dive into the questions, here is the code for the LinkedList class we will be using in this post:

class LinkedList: # ----------------------Nested Node Class ---------------------- class Node: def __init__(self, data=0, next=None): self.data = data self.next = next # ---------------------- LinkedList methods ------------------------- # Create an empty Linked List def __init__(self): self.head = None # Add Node to the end of the list def append(self, data): if self.head == None: self.head = LinkedList.Node(data) return current = self.head while (current.next != None): current = current.next current.next = LinkedList.Node(data) # Print the list def print_list(head): if head == None: print('[]') return current = head while (current != None): print(f'{current.data}', end=" | ") current = current.next print()

## Question # 1 – Find the Middle of a Linked List in One Pass

Companies –> Amazon, Apple, Adobe, Google

**Question:**

Return the middle node given the head of a singly-linked list.

Complete the algorithm in one pass of the list.

If there are two middle nodes, return the second.

**Constraints:**

- The number of nodes in the list is in the range
`[1, 100]`

. `1 <= Node.val <= 100`

**Example 1:**

Input: head = [7, 8, 9]Output: [8, 9]Reason: The middle node of the list is node 8.

**Example 2:**

Input: head = [7, 8, 9, 10]Output: [9, 10]Reason: Since the list has 2 middle nodes (8 and 9), we return the 2nd one.

## Solution to Question # 1

Here is what the skeleton to solution 1 looks like:

def middleNode(head): """Finds and returns the middle node in one pass Args: head (Node): The head of a singly linked list Returns: (Node): The middle node of a singly linked list """

**Our Intuition Tells Us…**

At first glance, I would assume I need to find the middle by first counting the number of nodes.

Then, we would need to take that number, divide it by two, and re-traverse to that index in the list. However, counting the number of nodes would take an entire pass of the list in and of itself.

So, how do we do this in one pass?

**Here’s a “Pointer”**

The trick is to use a pointer! This solution is what separates programmers from the rest of the pack. Knowing how pointers work and when to use them will open up an entirely new world for you.

**Here is the solution:**

def middleNode(head): mid = curr = head i = 1 while curr.next != None: curr = curr.next i += 1 if (i % 2 == 0): mid = mid.next return mid if __name__ == '__main__': ll = LinkedList() lst = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] for i in lst: ll.append(i) print_list(ll.head) print(f'Middle Node: {middleNode(ll.head).data}') ll.append(12) print_list(ll.head) print(f'Middle Node: {middleNode(ll.head).data}')

**Output:**

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |

Middle Node: 6

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |

Middle Node: 7

You need to initialize two pointers (**mid** and **curr)** and set them both equal to the **head** **node **of the list.

You will increment **curr **every iteration of the loop, and **mid** every two iterations. By doing this, the **curr** pointer will reach the end of the list twice as fast as **mid**. In other words, when **curr **reaches the end of the list **mid** will be at the **middle node.**

Return the **node **pointed to by the **mid **pointer and you’re finished.

**Time Complexity**

Since we complete this in one pass, the time complexity is **O(n).**

### Space Complexity

Since we just use two pointers, the space complexity is **O(1).**

## Question # 2 – Detect a Loop in a Linked List

Companies –> Amazon, Google, Microsoft, Visa, NVIDIA, Oracle, Facebook, Apple, Bloomberg, Spotify

**Question:**

Given the head of a linked list, determine if there is a loop in it.

There is a loop in the linked list if there is a node that can be reached again by continually following the next pointer.

Return **True **if there is a loop, else return **False**.

**Constraints:**

- The number of nodes in the list is in the range
`[0, 10`

.^{4}] `-10`

^{5}<= Node.val <= 10^{5}`pos`

is`-1`

or a**valid index**in the linked list.

**Example 1:**

Input: head = [7, 8, 9, 10]Output: TrueReason: There is a loop in the linked list, where the tail connects to the 1st node

**Example 2:**

Input: head = [2]Output: FalseReason: No loop in linked list

## Solution to Question # 2

Here is what the skeleton to solution 2 looks like:

def hasLoop(head): """If LinkedList has loop, return True Else return False Args: head (Node): The head of a Singly-linked list Returns: (bool): Whether or not the List contains a loop """

**Good Solution – Hashing Approach**

def detectLoop(head): curr = head visited = {} while curr: if curr in visited: return True visited[curr] = curr curr = curr.next return False if __name__ == '__main__': ll = LinkedList() lst = [7, 8, 9, 10] for i in lst: ll.append(i) ll.head.next.next.next.next = ll.head.next print(detectLoop(ll.head)) ll2 = LinkedList() ll2.append(2) print(detectLoop(ll2.head))

**Output:**

True

False

If a node is visited twice it is cyclic. We can accomplish “marking” off visited nodes by adding them to a hash table. A hash table will use a “hash” function to translate a “key” (or in this case the node pointer) to an index in an array.

Before adding a node to the hash table, check if it is already in there. If it is, it has already been visited and the linked list has a loop – return True.

**Time Complexity**

Since we visit each node at most once and since hashing is constant, the time complexity is **O(n) + O(1) = O(n).**

### Space Complexity

We will add at most n elements to the hash table, so the worst-case Space Complexity is **O(n).**

**Better Solution – Floyd’s Cycle Finding Algorithm**

def detectLoop(head): slow_pointer = head fast_pointer = head while(fast_pointer and fast_pointer.next): slow_pointer = slow_pointer.next fast_pointer = fast_pointer.next.next if slow_pointer == fast_pointer: return True return False if __name__ == '__main__': ll = LinkedList() lst = [7, 8, 9, 10] for i in lst: ll.append(i) print(ll.head.next.data) ll.head.next.next.next.next = ll.head.next print(detectLoop(ll.head)) ll2 = LinkedList() ll2.append(2) print(detectLoop(ll2.head))

**Output:**

True

False

**Two Runners**

Here is a hint: use two pointers as we did in question number one. Use one slow and one fast pointer, like runners on a circular track. If you send one runner out a bit faster than the other, they are bound to meet at some point on the track (if the track is circular). However, if it’s just a straight track (no loops) they will not meet.

Instead of using a hashmap, let’s use two pointers. We’ll name one **slow_pointer **and one **fast_pointer**, and set them both equal to the **head node**.

Then, we set a * while loop* with conditions that none of the pointers should be

**NULL (‘None’ in Python)**. The only case in which a pointer will point to

**NULL**is if there is no loop in the list, and the pointers iterate past the last node. In other words, we’ve exited the linked list; no loop was found.

Inside the loop, we increment the **slow_pointer** by one and the **fast_pointer** by two. If the two pointers are pointing to the same node at any point, it means there is a loop in the linked list and we return **True**.

**Time Complexity**

Since we will do at most one traversal of the list, the time complexity is **O(n).**

### Space Complexity

Since we only take up the space of 2 pointers, the space complexity is **O(1).**

## Question # 3 – Delete Nth-From-End Node of Linked List

Companies –> Facebook, Microsoft, Amazon, Google, Apple, Bloomberg, Paypal

**Question:**

Given the head of a linked list, delete Nth Node from the end of List.

Return the head.

**Constraints:**

- The number of nodes in the list is
`s`

. `1 <= s <= 30`

`0 <= Node.val <= 100`

`1 <= n <= s`

**Example 1:**

Input: head = [1, 2, 3], n = 2Output: [1, 3]

**Example 2:**

Input: head = [1, 3], n = 2Output: [3]

**Example 3:**

Input: head = [3], n = 1Output: []

## Solution to Question # 3

Here is what the skeleton to solution 3 looks like:

def removeNthFromEnd(head, n): """Given the head of a LinkedList, delete Nth Node from end of List Args: head (Node): The head of a Singly-linked list n (int): an integer indicating the number of nodes from the end of list to delete Returns: (Node): The head of a singly linked list """

**Good Solution – Two Passes – Find Length of List**

def removeNthFromEndTwoPass(head, n): length = 0 curr = head # Count length of list while curr: length += 1 curr = curr.next # If deleting head of list if length == n: return head.next length -= n + 1 curr = head # Iterate to Node before Node-to-be-removed while length: length -= 1 curr = curr.next curr.next = curr.next.next return head if __name__ == '__main__': ll = LinkedList() lst = [1, 2, 3] for i in lst: ll.append(i) print_list(ll.head) temp_head = removeNthFromEndTwoPass(ll.head, 2) print_list(temp_head) temp_head = removeNthFromEndTwoPass(ll.head, 1) print_list(temp_head) temp_head = removeNthFromEndTwoPass(ll.head, 1) print_list(temp_head)

**Output:**

**1 | 2 | 3 | ****1 | 3 | ****1 | ****[]**

Our intuition tells us to find the length of the list, but that in itself takes an entire pass of the list. Regardless, we’ll code it as our naive solution.

Then we check if **length == n. **If **truthy,** the **head** is the **node** to be removed. We then return **head.next**. But if **length != n, **we are not deleting the head so we can skip this block.

Now we need to find out *what* node from the beginning of the list we need to delete. We already have the **length** and **n (node to delete from the end)**. So, subtract **(n + 1)** from **length** to discover how many nodes you must traverse from the head.

When the loop exits, the **curr node** should point at the node * before* the node we want to delete. So, we just write one final line:

**curr.next = curr.next.next.**

Return the **head**.

**Time Complexity**

We traversed the list one time to find the length **O(L) **and the second time to find the **(L-n+1) node. **So the **Big O is O(2L-N+1) = O(n)**

### Space Complexity

We only used a pointer in each iteration, so space complexity is **O(1).**

**Better Solution – One Pass = Use Slow and Fast Pointer**

def removeNthFromEndOnePass(head, n): slow = fast = head # Send fast pointer to nth node for _ in range(n): fast = fast.next # Fast == None, delete head if fast == None: return head.next # Iterate slow/fast pointers so they stay 'n' nodes away from eachother while fast.next: slow = slow.next fast = fast.next # When fast.next is null, delete slow.next slow.next = slow.next.next #Finally, return head return head if __name__ == '__main__': ll = LinkedList() lst = [1, 2, 3, 4, 5] for i in lst: ll.append(i) print_list(ll.head) temp_head = removeNthFromEndOnePass(ll.head, 2) print_list(temp_head) temp_head = removeNthFromEndOnePass(temp_head, 4) print_list(temp_head) temp_head = removeNthFromEndOnePass(temp_head, 1) print_list(temp_head) temp_head = removeNthFromEndOnePass(temp_head, 2) print_list(temp_head) temp_head = removeNthFromEndOnePass(temp_head, 1) print_list(temp_head)

**Output:**

**1 | 2 | 3 | 4 | 5 | ****1 | 2 | 3 | 5 | ****2 | 3 | 5 | ****2 | 3 | ****3 | ****[]**

**Two Runners – Nth Strides Away**

Example:

Args: head = [**1, 2, 3, 4, 5], n = 2**

Here is a hint: use two pointers as we did in question number one. Use one slow and one fast pointer.

First, we’re going to send the fast pointer out to the nth (2nd) Node.

At this point, if **fast_pointer == None**, then we know to delete the * head* because it takes 5 steps from the

**first***to*

**node**

**null.**Then, we create a **slow_pointer **and iterate the **slow** and **fast pointers **each by “1” until the **fast_pointer’s next node is null. **At that point, the loop breaks.

Set the **slow_pointer’s** **next node** to its **next.next** node, and you will have successfully **deleted the Nth-node-from-the-end a linked list**.

The 2nd from the last node has now been deleted from the list.

Return the head of Linked List [1, 2, 3, 5]

**Time Complexity**

Since we will do at most one traversal of the list, the time complexity is **O(n).**

### Space Complexity

Since we only take up the space of 2 pointers, the space complexity is **O(1).**

## Summary

Linked Lists are the basis for almost every other complicated data structure. In order to truly become a master in any undertaking, building a solid foundation is the best way. In addition, the more practice you get with interview questions from top companies the more you are likely to land that high-paying, cool job you’ve always wanted.

I’ll be back soon to write more articles with detailed explanations of random interview questions. I hope you enjoyed it!

If you’re looking for a course to master Python and increase your salary potential in the process, I recommend Mosh’s course linked below:

Complete Python Mastery – Code With Mosh

Tags: data structure, Interview, linked list, python