How to Answer: Return the middle node of a given linked list.
Advice and answer examples written specifically for a Python Beginner Level Linked Lists job interview.
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- 4Solution:
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 slowTime 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 LLTime complexity - O(nodeCount)
Space complexity - O(1)
Written by S. Kumar on May 21st, 2021