9 Python Beginner Level Linked Lists Interview Questions & Answers
Below is a list of our Python Beginner Level Linked Lists interview questions. Click on any interview question to view our answer advice and answer examples. You may view six answer examples before our paywall loads. Afterwards, you'll be asked to upgrade to view the rest of our answers.
1. Add two numbers from two separated singly-linked lists.
This interview question focuses on Python linked lists and values along with constraints.
You are given two numbers that are represented as two singly-linked lists. Each node of the linked list represents a digit in the number. The digits are stored in reverse order. That is, the unit-place digit is the head of the linked list. Your task is to find the sum of the two numbers and return the result in the form of a linked list.
/*Example*/
Let two numbers are 123 and 456
so given linked lists will be
3 -> 2 -> 1
and 6 -> 5 -> 4
The sum of the numbers is 579
So the expected result will be
9 -> 7 -> 5
Constraints: The numbers of nodes in each given linked lists will be between 1 and 100
Solution:
The first solution that comes to mind is to get the value numbers from given linked lists. Then add them, and then create a linked list from the result again.
But the number of the digits in the list is up to 100, which means the range of the numbers is [1, 10100], which is too large for storing numbers directly in their bit forms in a computer.
What we can do is take digits one by one from the linked lists and add them. If it is smaller than 10, directly append it to the resultant list; if it is greater than 10, then append its unit place to the list and forward carry 1 to the next digits as we do in pen-paper while adding two numbers.
More formally,
Let, a and b are the linked lists and res be result list.
ai and bi are digits stored in the ith node.
ri = ai + bi + ci - 1 // take carry from last calculation
resi = ri % 10 // store the unit place i.e. remainder by 10
ci = floor(ri / 10) // forward carry, if any
class ListNode:
def __init__(self, val=0):
self.val = val
self.next = None
def addTwoNumbers(l1,l2):
newLL = ListNode()
remainder = 0
temp = newLL
while l1 or l2:
digit1 = l1.val if l1 else 0
digit2 = l2.val if l2 else 0
value = digit1 + digit2 + remainder
node = ListNode(value % 10)
remainder = value // 10
# move to next pointers
l1 = l1.next
l2 = l2.next
temp.next = node
temp = temp.next
if remainder:
temp.next = ListNode(remainder)
return newLL.next
Time complexity - O(max(n, m)) // n and m are length of the two digits
Space complexity - O(1)
Written by S. Kumar on May 21st, 2021
2. Return the middle node of a given linked list.
This interview question concentrates on using Python methods and linked lists.
You are given a linked list. You need to return the middle node of the linked list. If there are two middle nodes (the list is of even size), then return the second node.
/*Example*/
Given list- 1 -> 2 -> 3 -> 4 -> 5
expected returned node- 3
Given list- 1 -> 2 -> 3 -> 4 -> 5 -> 6
expected returned node- 4
Solution:
Approach I (two pointers):
Make two pointers slow and fast. When a fast pointer reaches the end of a linked list then the slow pointer points to the last node in the first half of the linked list. If the fast.next is not None then list is of even length and hence to get the first node in the second half of the linked list return slow.next.
class ListNode:
def __init__(self, val=0):
self.val = val
self.next = None
def findMiddleElement(head):
'''
slow move one step and fast move two step at a time
'''
slow, fast = head, head
while fast.next and fast.next.next:
fast = fast.next.next
slow = slow.next
if fast.next:
return slow.next
return slow
Time complexity - O(nodeCount)
Space complexity - O(1)
Approach II (list length):
The solution is quite simple. We will count the total number of nodes in the list. Then we will find the index of the middle element by dividing it by 2.
Let nodeCount be total number of nodes
if nodeCount is odd, the middle element is at index floor(nodeCount / 2).
For example, if nodeCount = 5, middle element element is at index floor(5 / 2) = 2
if nodeCount is even, the middle element is at index nodeCount / 2.
For example, if nodeCount = 6, middle element element is at index 6 / 2 = 3
class ListNode:
def __init__(self, val=0):
self.val = val
self.next = None
def length(LL):
''' returns count of linked list '''
count = 0
while LL:
LL = LL.next
count += 1
return count
def findMiddleElement(LL):
''' return the middle node based on length of linked list '''
len_LL = length(LL)
mid_index = len_LL // 2
while mid_index:
mid_index -= 1
LL = LL.next
return LL
Time complexity - O(nodeCount)
Space complexity - O(1)
Written by S. Kumar on May 21st, 2021
3. Remove elements from linked list that are equal to target.
This interview question shows the developer's ability to use Python recursion and iteration.
You are given the head of a linked list. You are also given a target value. Your task is to remove all the nodes from the linked list whose value is equal to the target.
/*Example*/
Given: linked list => 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6 target = 6
Expected output: 1 -> 2 -> 3 -> 4 -> 5
Solution:
Approach I (recursive):
In the recursive approach, we will check the value of the current node in the function call. If the value of the current node i.e. head in the function call is equal to target, we return next of head instead of returning head. Before doing that, we recursively check and remove the next of head. For example:- for list 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6, the calls are:
(rm denotes the function removeElements)
|rm(1)
| |rm(2)|
| | |rm(6)|
| | | |rm(3)|
| | | | |rm(4)|
| | | | | |rm(5)|
| | | | | | |rm(6)|
| | | | | | | |rm(null)
| | | | | | | | return null
| | | | | | | |head.next = null
| | | | | | | |head.val == 6; // 6 == 6 => true
| | | | | | | |return head.next(null)
| | | | | | |head.next = null
| | | | | | |head.val == 6; // 5 == 6 => false
| | | | | | |return head(5)
| | | | | |head.next = 5
| | | | | |head.val == 6 // 4 == 6 => false
| | | | | |return head(4)
| | | | |head.next = 4
| | | | |head.val == 6 // 3 == 6 => false
| | | | |return head(3)
| | | |head.next = 3
| | | |head.val == 6 // 6 == 6 => true
| | | |return head.next(3)
| | |head.next = 3
| | |head.val == 6 // 2 == 6 => false
| | |return head(2)
| |head.next = 2
| |head.val == 6 // 1 == 6 => false
| |return head(1)
The resulting list is the return of all the function calls i.e. 1 -> 2 -> 3 -> 4 -> 5
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def removeElements(head: ListNode, target: int) -> ListNode:
if not head:
return None
head.next = removeElements(head.next, target)
return head.next if head.val == target else head
n = length linked list
Time complexity- O(n)
Space complexity- O(n)
Approach II (iterative):
In the iterative approach, we loop over all the nodes in the list. From the current node curr, if it has a next node (curr.next) and its value is equal to the target, we will remove the next node. To remove we will set the next of curr to the next of curr.next.
After the loop, all the nodes with value target will be removed except at the head. So after the loop, we will check for the head node too.
class ListNode:
def __init__(self, val = 0, next = None):
self.val = val
self.next = next
def removeElements(head: ListNode, target: int) -> ListNode:
if head is None: return head
curr = head
while curr and curr.next:
if curr.next.val == target:
curr.next = curr.next.next
else:
curr = curr.next
return head if head.val != target else head.next
n = length linked list
Time complexity- O(n)
Space complexity- O(1)
Written by S. Kumar on May 21st, 2021
4. Delete the node in a singly-linked list.
This question focuses on Python iteration.
You are given a node nodeToDelete of a singly linked list. Your task is to delete this node. This is guaranteed that the given node will not be the tail node of the linked list. Please note that you are not given the head of the linked list. You don’t have to return anything, just update the list in place.
/*Example*/
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
|
given node
Expected output list: 1 -> 2 -> 4 -> 5 -> 6 -> 7
Solution:
We will iterate over all the nodes after nodeToDelete. Let curr be the current node. We will copy the value of the next to the current node. Thus the value of the node to be deleted will be replaced with the value of the next node. For example the given list 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 and 3 be the node to be deleted:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
|
curr
1 -> 2 -> 4 -> 4 -> 5 -> 6 -> 7
|
curr
1 -> 2 -> 4 -> 5 -> 5 -> 6 -> 7
|
curr
1 -> 2 -> 4 -> 5 -> 6 -> 6 -> 7
|
curr
When we are the second last node (i.e. curr.next.next is null), we will copy the value of the last node and then we will delete the last node by setting curr.next = null.
1 -> 2 -> 4 -> 5 -> 6 -> 7 -> 7 (copy)
|
curr
1 -> 2 -> 4 -> 5 -> 6 -> 7 (delete last node)
|
curr
class ListNode:
def __init__(self, data):
self.val = data
self.next = None
def deleteNode(nodeToDelete: ListNode) -> ListNode:
curr = nodeToDelete
while curr.next:
node.val = node.next.val
# curr.next is last node
if node.next.next is None:
node.next = None
break
node = node.next
n = length linked list
Time complexity- O(n)
Space complexity- O(1)
Written by S. Kumar on May 21st, 2021
5. Merge two sorted lists.
This interview question focuses on the developer's ability to use Python iteration.
You are given two sorted singly-linked lists. Your task is to merge both linked lists and return them to a new linked list.
/*Example*/
Given: l1 = [1, 3, 4] l2 = [2, 5, 6]
Expected output: [1, 2, 3, 4, 5, 6]
Solution:
We will iterate over all the nodes of the lists. We will have two pointers curr1 and curr2 pointing to the current nodes we are processing for both the lists. We will compare the values of the current node for curr1 and curr2 and choose the linked list with the smaller value. For example, if curr1 has a smaller value than curr2, we will create a new node with the value curr1.val and assign this as the next node to curr and advance curr1 and curr by using curr1 = curr1.next and curr = curr.next and same for curr2.
At the end, when either one or both the linked list ends up we check if any of the linked lists is still unfinished. If yes then we assign the rest of the remaining linked list (curr1 or curr2) to curr while creating a new node for every node in the remaining linked list curr1 or curr2.
After initialising, the new list dummy is:
0
after the first iteration
0 -> 1
after the second iteration
0 -> 1 -> 2
after the third iteration
0 -> 1 -> 2 -> 3
after the third iteration
0 -> 1 -> 2 -> 3 -> 4
..
..
after the final iteration
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6
So our resulting list starts from the second node of the list starting with dummy i.e. dummy.next.
class ListNode:
def __init__(self, val = 0, next = None):
self.val = val
self.next = next
def mergeLists(l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode()
curr = dummy
curr1, curr2 = l1, l2
while curr1 and curr2:
if curr1.val < curr2.val:
newNode = ListNode(curr1.val)
curr1 = curr1.next
else:
newNode = ListNode(curr2.val)
curr2 = curr2.next
curr.next = newNode
curr = curr.next
while curr2:
curr.next = ListNode(curr2.val)
curr = curr.next
curr2 = curr2.next
while curr1:
curr.next = ListNode(curr1.val)
curr = curr.next
curr1 = curr1.next
return dummy.next
m = length first linked list
n = length second linked list
Time complexity- O(m + n)
Space complexity- O(1)
Written by S. Kumar on May 21st, 2021
6. Can you remove nodes between indices from list1 and replace them with list2 nodes?
This question concentrates on the developer's knowledge of Python indices and lists.
You are given two singly-linked lists list1 and list2. You are also given two 0-based indices start and end. The two given indices are corresponding to list1. Your task is to remove the nodes between indices start and end of list1 both inclusive and place list2 in place of the deleted nodes.
/*Example*/
Given:
list1 = 11 -> 12 -> 13 -> 14 -> 15 -> 16
list2 = 21 -> 22
start = 2 end = 4
Expected output: 11 -> 12 -> 21 -> 22 -> 16
Explanation:
list1 = 11 -> 12 -> 13 -> 14 -> 15 -> 16
indices = 0 1 2 3 4 5
| |
start end (these nodes are deleted)
11 -> 12 13 -> 14 -> 15 16
\ /
---> 21 -> 22 --->
Constraint
â— 3 <= list1.length
â— 1 <= a <= b < list.length - 1
â— 1 <= list2.length
Solution:
First, we find the start and the end nodes of list2. These are represented by list2FirstNode and list2LastNode. After that, we find the pointers to nodes at index start - 1 and end + 1. For the given example, to find the node at index start - 1,
11 -> 12 -> 13 -> 14 -> 15 -> 16
|
curr
i = 0
11 -> 12 -> 13 -> 14 -> 15 -> 16
|
curr
i = 1 (we stop here as i == start - 1)
After we get the node at index start - 1, we first store a reference to the next node (node at index start) in temp and then assign it’s next to list2FirstNode. Then we again iterate over list1 to get a reference to the node at index end + 1 and assign the next of list2LastNode to this node.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeInBetween(list1: ListNode, start: int, end: int, list2: ListNode) -> ListNode:
list2FirstNode = list2
list2LastNode = list2
while list2LastNode.next:
list2LastNode = list2LastNode.next
i = 0
curr = list1
while i < start - 1:
curr = curr.next
i += 1
temp = curr.next
curr.next = list2FirstNode
# curr holds the node at index start
curr = temp
i += 1
while i <= end:
i += 1
curr = curr.next
list2LastNode.next = curr
return list1
n = length second linked list
Time complexity- O(end + m)
Space complexity- O(1)
Written by S. Kumar on May 21st, 2021
7. Create a deep copy of the special-linked list.
This interview question shows the developer's ability to work with Python loops.
You are given the head node of a linked list. The linked list is special. In addition to the value of the node and next pointer of the node, the nodes contain additional pointer random. This random pointer points to any random point of the list. It may be null also.
Your task is to create a deep copy of the list. There must be new nodes created corresponding to each node in the given list. Their next and random pointers must point to nodes with the same value as in the given list. None of the pointers in the new list should point to nodes in the given list. Return the head of the new list created.
/*Example*/
Given list
1 -> 2 -> 3 -> 4 -> 5 -> 6
| | | | | |
--->-|-->-- | | |
--<----<--|--<-- |
--->--->---
That is,
1.random = 3
2.random = null
3.random = null
4.random = 6
5.random = 2
6.random = null
Expected output:
1 -> 2 -> 3 -> 4 -> 5 -> 6
| | | | | |
--->-|-->-- | | |
--<----<--|--<-- |
--->--->---
(We need the exact same list but deep copied.)
Solution:
First, we will create new nodes with values in the original list. For every node in the original list, we will create a new node with the same value and store it in a map reference. The keys of references will be the references of nodes in the original list and the values will be references to corresponding new nodes created. For example,
Let’s say original_{val} be the node in the original list with value val, and new_{val} be the corresponding new node created. After iterating over all the nodes, the map references look like:
{
original_1 -> new_1
original_2 -> new_2
original_3 -> new_3
original_4 -> new_4
original_5 -> new_5
original_6 -> new_6
}
After this, we will again iterate over the original list, and will assign corresponding next and random pointers to the new nodes. For one iteration, say curr = original_1, the value of variables in the loop are:
curr = original_1
curr.next = original_2
curr.random = original_3
---------------------------
newNode = new_1
newNode.next = new_2
newNode.random = new_3
class Node:
def __init__(self, val, next = None, random = None):
self.val = val
self.next = next
self.random = random
def copySpecialList(head: Node) -> Node:
if not head:
return head
references = {}
curr = head
while curr:
node = Node(curr.val)
references[curr] = node
curr = curr.next
curr = head
while curr:
newNode = references[curr]
newNode.next = references.get(curr.next, None)
newNode.random = references.get(curr.random, None)
curr = curr.next
return references[head]
n = length the linked list
Time complexity- O(n)
Space complexity- O(n)
Written by S. Kumar on May 21st, 2021
8. Does the list contain a cycle?
This question focuses on Python pointers.
You are given the head of a singly linked list. Your task is to check if the list contains a cycle of not.
/*Example*/
Given list: 1 -> 2 -> 3 -> 4 -> 5
Expected output: false
Given list: 1 -> 2 -> 3 -> 4 -> 5
| |
---<---<---<----
Expected output: true
Solution:
This is a very famous problem with a famous solution. The solution is known as fast-slow pointers. We will have two pointers: slow and fast. In every iteration, we will advance slowly by one step while we advance fast by two steps.
â— If there is no cycle, the loop will break, as either fast.next or fast.next.next will be null and we will return false.
â— If there is a cycle, after the last node, the fast pointer will be in the cycle. It will always be in the cycle. Since the difference of steps between the fast and slow pointer that they take is one only, there will be a point when they both point to the same node. When they do so, we will return true.
For example 2, given list: 1 -> 2 -> 3 -> 4 -> 5 (5.next = 2 i.e. there is a cycle but we are not showing it here for simplicity)
-> slow
|
1 -> 2 -> 3 -> 4 -> 5
|
fast
-----------------------------------------------
slow
|
1 -> 2 -> 3 -> 4 -> 5
|
fast
-----------------------------------------------
slow
|
1 -> 2 -> 3 -> 4 -> 5
|
fast
-----------------------------------------------
slow
|
1 -> 2 -> 3 -> 4 -> 5
|
fast (fast pointer is in cycle now, 5.next.next = 2.next = 3)
-----------------------------------------------
slow
|
1 -> 2 -> 3 -> 4 -> 5
|
fast (both point to the same node, return true)
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def hasCycle(head: ListNode) -> ListNode:
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
n = length the linked list
Time complexity- O(n)
Space complexity- O(1)
Written by S. Kumar on May 21st, 2021
9. How do you rotate the list?
This interview question shows the developer's ability to work with Python list length.
You are given the head node of a singly linked list. You are also given an integer k. Your task is to rotate the list right by k places.
/*Example*/
Given list: 1 -> 2 -> 3 -> 4 -> 5 k = 2
Expected output: 4 -> 5 -> 1 -> 2 -> 3
Explanation:
After 1st rotation: 5 -> 1 -> 2 -> 3 -> 4
After 2nd rotation: 4 -> 5 -> 1 -> 2 -> 3
Solution:
We first find the length of the list, let it be len. The value of k can be anything, even 0 or greater than len. The list after k rotations and the list after k + len rotations will be the same. So we normalize the value k. We take a modulo of k with len. Now the value lies between 0 and len - 1. If k is 0, then no rotation is required. So we return the head without modifying anything. Otherwise, we iterate over the list. As observed from the example, if the rotations required are 2, 2 nodes from the end of the list will become forward. The first (len - k) nodes will be the tail. The (len - k)th node (1-indexed) will be the last node in the list after k rotations. Thus we iterate over the list and find the (len - k)th node.
The new head of the new list will be (len - k + 1)st i.e. next of (len - k)th. Then iterate up to the last node of the list. After finding the last node, we set it’s next to the original head.
For the given example, len = 5, k = 2
newHead
|
1 -> 2 -> 3 -> 4 -> 5
|
(len - k)th node (this node will be the last node in the new list, we set it’s next to null after finding it)
class ListNode:
def __init__(self, val = 0, next = None):
self.val = val
self.next = next
def rotateRight(head: ListNode, k: int) -> ListNode:
if not head: return None
length = 0
curr = head
while curr:
curr = curr.next
length += 1
k = k % length
if k == 0: return head
i = 1
curr = head
while i < (length - k):
curr = curr.next
i += 1
newHead = curr.next
curr.next = None
curr = newHead
while curr.next:
curr = curr.next
curr.next = head
return newHead
n = length the linked list
Time complexity- O(n)
Space complexity- O(1)
Written by S. Kumar on May 21st, 2021