Find the middle of a given linked list
Given a singly linked list, find the middle of the linked list. For example, if the given linked list is 1->2->3->4->5 then the output should be 3.
If there are even nodes, then there would be two middle nodes, we need to print the second middle element. For example, if given linked list is 1->2->3->4->5->6 then the output should be 4.
Python program to find middle of a linked list using one traversal
Given a singly linked list, find middle of the linked list. Given a singly linked list, find middle of the linked list. For example, if given linked list is 1->2->3->4->5 then output should be 3.
Method 1:
Traverse the whole linked list and count the no. of nodes. Now traverse the list again till count/2 and return the node at count/2.
Method 2:
Traverse linked list using two pointers. Move one pointer by one and other pointer by two. When the fast pointer reaches end slow pointer will reach middle of the linked list.
# Python 3 program to find the middle of a
# given linked list
# Node class
class Node:
# Function to initialise the node object
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
# Function to get the middle of
# the linked list
def printMiddle(self):
slow_ptr = self.head
fast_ptr = self.head
if self.head is not None:
while (fast_ptr is not None and fast_ptr.next is not None):
fast_ptr = fast_ptr.next.next
slow_ptr = slow_ptr.next
print("The middle element is: ", slow_ptr.data)
# Driver code
list1 = LinkedList()
list1.push(5)
list1.push(4)
list1.push(2)
list1.push(3)
list1.push(1)
list1.printMiddle()
|
Method 3:
Initialized the temp variable as head
Initialized count to Zero
Take loop till head will become Null(i.e end of the list) and increment the temp node when count is odd only, in this way temp will traverse till mid element and head will traverse all linked list. Print the data of temp.
# Python 3 program to find the middle of a
# given linked list
class Node:
def __init__(self, value):
self.data = value
self.next = None
class LinkedList:
def __init__(self):
self.head = None
# create Node and and make linked list
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
def printMiddle(self):
temp = self.head
count = 0
while self.head:
# only update when count is odd
if (count & 1):
temp = temp.next
self.head = self.head.next
# increment count in each iteration
count += 1
print(temp.data)
# Driver code
llist = LinkedList()
llist.push(1)
llist.push(20)
llist.push(100)
llist.push(15)
llist.push(35)
llist.printMiddle()
# code has been contributed by - Yogesh Joshi
|
Middle of the Linked List
Difficulty: Easy
Understanding the Problem
Problem Description
Given a non-empty, singly linked list with head node head, write a program to return a middle node of the linked list. If there are even nodes, then there would be two middle nodes, we need to print the second middle element.
Example 1
Input: 11->2->13->44->5 Output: 13 Explanation: The middle element of the linked list is 13.Example 2
Input: 10->2->34->24->15->60 Output: 24 Explanation: As there are even number of nodes, return 24 as it is the second node among two middle elements.Solutions
- Two-Pass: Find the length of the linked list and return the (length/2)th node.
- One-Pass: Use two pointers, the 2nd pointer should traverse twice as fast at the first.
Before moving forward with the question, you must understand the properties of a linked list.
You can try this problem here.
1. Two-Pass
The question demands to find the middle of a singly linked list. We can simply find the total length of the linked list, in this way we can identify which node falls in the middle. To find the middle node, we can traverse again until we reach (length/2)th node.
Solution Steps
- Create a pointer p, pointing to the head.
- Iterate over the linked list until p reaches to the end of the linked list, thereby find the length of the list.
- Set p to head again. Now, increment p length/2 times. Now, the p is at the middle of the linked list node. Return the value at p
Pseudo Code
int middleNode(ListNode head) { int l=0 ListNode p = head while (p != null) { p = p.next l = l + 1 } p = head int c = 0 while (c < l/2) { p = p.next c = c + 1 } return p.data }Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
Critical Ideas To Think
- Why did we reinitialize p with the head?
- Which node will be returned if the length of the linked list is even?
- What if the linked list forms a loop?
2. One-Pass
Another way to solve this problem is to use a little trick. Instead of traversing twice, we can create two-pointers say slow_ptr and fast_ptr.We can make the fast_ptr twice as fast as slow_ptr. So, When the fast_ptr will reach to the end of the linked list, slow_ptr would still be at the middle, thereby pointing to the mid of the linked list.
Solutions Steps
- Create slow_ptr and fast_ptr pointing to the head initially.
- Increment fast_ptr by 2 and slow_ptr by 1 positions until fast_ptr and fast_ptr.next is not NULL
- Return the value at slow_ptr.
Pseudo Code
int middleNode(ListNode head) { ListNode slow = head ListNode fast = head while (fast != null and fast.next != null) { slow = slow.next fast = fast.next.next } return slow.data }Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
Critical Ideas To Think
- Why did we use two pointers?
- Why did we iterate until fast != null and fast.next != null ?
- Do both the discussed approaches affect the running time?
Comparison Of Different Approaches
Suggested Problems To Solve
- Remove Duplicates from Sorted List
- Merge Sort on Linked List
- Check if a singly linked list is a palindrome
- Detect and Remove Loop in a Linked List
- Sort a linked list using insertion sort
- Remove Nth Node from List End
Happy coding!
Enjoy Algorithms.