3 Python Intermediate Level Linked Lists Interview Questions & Answers
Below is a list of our Python Intermediate Level Linked Lists interview questions. Click on any interview question to view our answer advice and answer examples. You may view 5 answer examples before our paywall loads. Afterwards, you'll be asked to upgrade to view the rest of our answers.
1. Remove the duplicates from this sorted singly linked list.
This interview question concentrates on using Python duplicates and linked lists.
You are given a sorted singly linked list. You need to remove the duplicates from the linked list and return their head node. The returned list must also be a sorted list.
/*Example*/
Given list- 1 -> 1 -> 2
expected output- 1 -> 2
Given list- 1 -> 2 -> 2 -> 3 -> 4 -> 4 -> 4
expected output- 1 -> 2 -> 3 -> 4Solution:
We will traverse the whole list. If we find a duplicate, we will delete it.
Let curr be the pointer to the current at which we are. It will point to the first occurrence of a number.
Let nextNode be the next node of curr.
We will compare the value of curr with the value of nextNode-
-> if the values are not equal, it means we don’t have any more duplicate corresponding to the value of curr, we will update curr to point to the next node.
-> if the values are equal, we will delete nextNode. We will delete nextNode by pointing next of curr to next of nextNode. So in the illustration below, curr is at 41 and nextNode is at 42. Their values are equal. So we will delete 42. We will point the next pointer of 41 to the next of 42 i.e. 43.
(The subscript shows the identity of nodes corresponding to the same value)
nextNode
|
0 -> 1 -> 2 -> 3 -> 41 -> 42 -> 43 -> 44 -> 5
| |
curr nextNode.next
After deleting nextNode (42)-
nextNode
|
0 -> 1 -> 2 -> 3 -> 41 -> 43 -> 44 -> 5
| |
curr nextNode.next
class ListNode:
def __init__(self, val=None):
self.val = val
self.next = None
def findMiddleElement(head):
curr = newLL = ListNode(None)
while head:
if curr.val == head.val:
head = head.next
continue
curr.next = ListNode(head.val)
# move both pointers
curr = curr.next
head = head.next
return newLL.nextTime complexity - O(n)
Space complexity - O(1)
Written by S. Kumar on May 22nd, 2021
2. Given the head of a singly linked list, return the reversed list.
This interview question concentrates on using Python recursive and iterative functions.
Given the head of a singly linked list, reverse the list, and return the reversed list.
/*Example*/
Given: 1 -> 2 -> 3 -> 4 -> 5
Expected output: 5 -> 4 -> 3 -> 2 -> 1Solution:
Approach I (Recursive):
We maintain the current node and the node next to this node.
In our reverse() function we are taking the current node and the previous node as the input arguments. It reverses a singly linked list.
We continue to call the function with the node next to the head as the current node and the head as the previous node till we have reached the last node.
For 1 -> 2 -> 3 once we have reached the last node it would look like 1 -> 2 -> 3 -> null. Thus we need to make the last node point to the second last node. Which will make the list as 1 -> 2 <- 3.
Going back through our recursive calls we do the same reversing and return the last node as the root in the end.
class ListNode:
def __init__(self, val=None):
self.val = val
self.next = None
def reverse(head, previous):
revLL = head
if head.next:
revLL = reverse(head.next, head)
head.next = previous
return revLL
def reverseLinkedList(head):
''' recursive '''
return reverse(head, None)Approach II (Iterative):
We wish to maintain three variables. current, next, and prev.
During every iteration, we copy the node next to the head into our next variable. We need to save this before we move forward and reverse the current node.
Then we make the head node point to the previous node. With this, we are reversing our current node to point to the previous node.
Next, we assign the prev variable to the current node. Thus when we iterate forward in our list the node next to this can be pointed to this.
Finally, we assign the next to the current node so that we can iterate forward in our list and repeat the process for the next nodes.
Once we are done with all of the iterations we notice that the head variable is pointing to nothing. Thus we swap its value with the prev variable.
def reverseLinkedList(head):
''' iterative '''
curr, prev = head, None
while curr:
# save the next pointer
next = curr.next
# make next point to prev
curr.next = prev
# update prev and current
prev = curr
curr = next
return prevTime complexity- O(n) n is the length of the list
Space complexity- O(1)
Written by S. Kumar on May 22nd, 2021
3. Where do the two linked lists intersect?
This question focuses on working with Python lists.
You are given heads of two singly linked lists: headA and headB. Your task is to return the node at which they intersect each other. If they don’t intersect, return null.
It is guaranteed that there is no cycle in any of the lists. Please note the linked lists MUST retain their original structure after the function returns.
/*Example*/
Given lists:
headA: 4 -> 1
\
8 -> 7 -> 9
/
headB: 5 -> 2 -> 3 -> 10
Expected output: 8
Explanation: Since both of the lists intersect at node 8, we return 8
Given lists:
headA: 4 -> 1 -> 8 -> 4 -> 5
headB: 5 -> 2 -> 3 -> 8 -> 4 -> 5
Expected output: null
Explanation: The lists do not intersect.Solution:
Approach I (finding length):
First, we will find the lengths of the two lists using the function listLength. Then we will align headA and headB such that the length of the list after points headA and headB are the same. For the first example:
lenA = 5
lenB = 7
We move headB two steps ahead to point to the node with value 3 such that lengths after headA and headB are the same, that is 5.
After aligning the nodes, we iterate over both lists simultaneously and will find the same node. At each iteration, we advance both headA and headB if previous values were not equal. We break the loop as soon as the values of headA and headB are the same which means it is the intersection node.
If the lists do not intersect, the values of headA and headB will be null at last, which will break the loop and will return null.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def listLength(head: ListNode) -> int:
count = 0
while head:
head = head.next
count += 1
return count
def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:
lenA = listLength(headA)
lenB = listLength(headB)
while lenA > lenB:
lenA -= 1
headA = headA.next
while lenB > lenA:
lenB -= 1
headB = headB.next
while headA is not headB:
headA = headA.next
headB = headB.next
return headAn = length the linked list
Time complexity- O(n)
Space complexity- O(1)
Written by S. Kumar on May 22nd, 2021