How do you find the middle element in a single traversal in a singly linked list?

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.

Table of Contents Show

• Find the middle of a given linked list
• Python program to find middle of a linked list using one traversal
• Middle of the Linked List
• How do you find the middle element in a single traversal in a singly linked list?
• How do you find the middle element of a linked list in one pass in C++?
• What is the time complexity for finding the middle node of a linked list?
• How to Find Middle Element of a Linked List?

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()

Output: The middle element is: 2

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

Output: 100

Article Tags :

Linked List

Python Programs

Python DSA-exercises

Python LinkedList-exercises

Technical Scripter 2018

Practice Tags :

Linked List

Read Full Article

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

1. Two-Pass: Find the length of the linked list and return the (length/2)th node.
2. 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.

How do you find the middle element in a single traversal in a singly 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.

How do you find the middle element of a linked list in one pass in C++?

In order to find middle element of linked list in one pass, you need to maintain two pointers, one increment at each node while other increments after two nodes at a time. By having this arrangement, when first pointer reaches end, second pointer will point to middle element of linked list.

What is the time complexity for finding the middle node of a linked list?

The running time of finding the middle element this way with two pointers is O(n) because once we pass through the entire linked list of n elements, the slower pointer is at the middle node already.

How to Find Middle Element of a Linked List?

Method 1: Finding middle element of a linked in two traversal

i) Traverse a linked list and find the length of a linked list.
ii) Once we know the length of a linked list. We can traverse again upto length/2 and print the value of a node present at mid position.

By using this method we can solve this problem in two traversal.

Can we do better than that? How do you find the middle element in a singly linked list in one pass?

Yes we can solve this problem in a single traversal. Let’s discuss our second approach.

Check if a linked list is palindrome or not

Sort a linked list of 0s, 1s and 2s

Method 2: Find middle element in linked list in one pass using two pointers.

i) Use two pointer slow and fast. Initialized both the pointers to the head of a linked list.
ii) Move fast pointer by two step and slow pointer by one step in each iteration.
iii) When fast pointer reaches at the end of a linked list, The slow pointer points to the middle element of a linked list.

Programming questions on linked list

Find Middle Element of a Linked List

C++ Code

Solution 2: [Efficient] Tortoise-Hare-Approach

Unlike the above approach, we don’t have to maintain nodes count here and we will be able to find the middle node in a single traversal so this approach is more efficient.

Intuition: In the Tortoise-Hare approach, we increment slow ptr by 1 and fast ptr by 2, so if take a close look fast ptr will travel double than that of the slow pointer. So when the fast ptr will be at the end of Linked List, slow ptr would have covered half of Linked List till then. So slow ptr will be pointing towards the middle of Linked List.

Approach:

1. Create two pointers slow and fast and initialize them to a head pointer.
2. Move slow ptr by one step and simultaneously fast ptr by two steps until fast ptr is NULL or next of fast ptr is NULL.
3. When the above condition is met, we can see that the slow ptr is pointing towards the middle of Linked List and hence we can return the slow pointer.

Code: