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

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.

Linked List Code 链表代码

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

在我们深入探讨问题之前,以下是我们将在本文中使用的LinkedList类的代码:

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

Input: head = [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:
      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 = 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):
    """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 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.

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!

发表评论

邮箱地址不会被公开。 必填项已用*标注