# Python中的面试问题–单链接列表

Interview Questions in Python – Singly-Linked-Lists

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.

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

# Create an empty Linked List
def __init__(self):

# Add Node to the end of the list
def append(self, data):
return
while (current.next != None):
current = current.next

# Print the list
print('[]')
return
while (current != None):
print(f'{current.data}', end=" | ")
current = current.next
print()```

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

Question:

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:

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):
i = 1
while curr.next != None:
curr = curr.next
i += 1
if (i % 2 == 0):
mid = mid.next
return mid

if __name__ == '__main__':
lst = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
for i in lst:
ll.append(i)

ll.append(12)

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, 104]`.
• `-105 <= Node.val <= 105`
• `pos` is `-1` or a valid index in the linked list.

Example 1:

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

Example 2:

Output: False
Reason: 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:

Returns:
(bool): Whether or not the List contains a loop
"""```

### Good Solution – Hashing Approach

```def detectLoop(head):
visited = {}

while curr:
if curr in visited:
return True
visited[curr] = curr
curr = curr.next

return False

if __name__ == '__main__':
lst = [7, 8, 9, 10]
for i in lst:
ll.append(i)

ll2.append(2)

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):
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__':
lst = [7, 8, 9, 10]
for i in lst:
ll.append(i)

ll2.append(2)

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

Question:

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

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 = 2
Output: [1, 3]

Example 2:

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

Example 3:

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

## Solution to Question # 3

Here is what the skeleton to solution 3 looks like:

```def removeNthFromEnd(head, n):
delete Nth Node from end of List
Args:
n (int): an integer indicating the number of nodes from the end of list to delete

Returns:
"""```

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

```def removeNthFromEndTwoPass(head, n):
length = 0
# Count length of list
while curr:
length += 1
curr = curr.next

# If deleting head of list
if length == n:

length -= n + 1
# Iterate to Node before Node-to-be-removed
while length:
length -= 1
curr = curr.next

curr.next = curr.next.next

if __name__ == '__main__':
lst = [1, 2, 3]
for i in lst:
ll.append(i)

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.

### 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):
# Send fast pointer to nth node
for _ in range(n):
fast = fast.next

# Fast == None, delete head
if fast == None:

# 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

if __name__ == '__main__':
lst = [1, 2, 3, 4, 5]
for i in lst:
ll.append(i)

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 node to 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.

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