Middle of the LinkedList Write a method that returns an intermediate node in a LinkedList, specifying the beginning of a single linked list. If the total number of nodes in the LinkedList is even, it returns the second intermediate node.
Input: 1 -> 2 -> 3 -> 4 -> 5 -> null Output: 3
Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null Output: 4
Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null Output: 4
Solution One of the brute force strategies is to first count the number of nodes in the LinkedList and then find the central node in the second iteration. It's important to be able to do this in a single iteration.
Use the fast and slow pointer methods to ensure that the fast pointer is always twice the node ahead of the slow pointer. Thus, when the fast pointer reaches the end of the LinkedList, the slow pointer points to the central node.
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
def find_middle_of_linked_list(head):
# Time Complexity O(N)
# Space Complexity O(1)
slow = head
fast = head
while (fast is not None and fast.next is not None):
slow = slow.next
fast = fast.next.next
return slow
def main():
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)
print("Middle Node: " + str(find_middle_of_linked_list(head).value))
head.next.next.next.next.next = Node(6)
print("Middle Node: " + str(find_middle_of_linked_list(head).value))
head.next.next.next.next.next.next = Node(7)
print("Middle Node: " + str(find_middle_of_linked_list(head).value))
main()
Recommended Posts