How do you find the middle of a linked list in Python?

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
Find the Middle element of Linked List in Python
Approaches to find the middle element of a Linked List:
Python program to find the middle element of a Linked List
Leave a Reply Cancel reply
Program to find the middle node of a singly linked list in Python
Middle of the Linked List

Find the Middle element of Linked List in Python

By Ashutosh Srivastava

In this tutorial, we will learn how to find the middle element of a linked list in Python.

Linked is a linear data structure. Each element consist of two items first being the data and the second being the reference to the next node item. The first node of the linked list is called as the head node. As compared to arrays linked lists are the better option for performing operations such as insertion and deletion, whereas arrays are good for accessing random elements of the arrays. These were the few things you needed to know before beginning with the linked list. In this tutorial, we are going to learn how to find the middle element of linked list in O(n).

Approaches to find the middle element of a Linked List:

Counting the number of elements in the linked list and then dividing by 2 to locate the middle element. This is what is known as the naive solution.
A better and effective way is to initialize two-variables and increase one of them by 1 and others by 2. So by the time, the latter one’s points to the null the other would have been at the center/middle.

The code to the second approach is given below but I highly recommend to try the approach first on your IDE first before looking at the code below.

Python program to find the middle element of a Linked List

class Node: def __init__(self,data): self.data=data self.next=None class Linked_List: def __init__(self): self.head=None self.root=None def print(self): temp=self.root while(temp): print(temp.data) temp=temp.next def push(self,data): new=Node(data) if(self.head==None): self.head=new self.root=new else: self.head.next=new self.head=new def middle(self): i1=i2=self.root if(i1 is not None): while(i1 is not None and i1.next is not None): i1=i1.next.next i2=i2.next print("Middle is: ",i2.data) if __name__=="__main__": llist=Linked_List() llist.push(1) llist.push(2) llist.push(3) llist.push(4) llist.push(5) llist.push(6) llist.push(7) llist.push(8) llist.push(9) llist.push(10) llist.middle()Output Middle is: 6

The class Node above is to initialize the node objects. Approach 2 is implemented in the function middle() of the Linked_List class. You can also use user input using the input() method. Instead of giving the inputs by yourself in the push method. list is the object of class Linked_List.

The code complexity for this approach is O(n), where n is the number of elements in the linked list.

[Note: In case of even elements in the list the later of middle 2 elements is called the middle. You can consider this to be a world convention.]

Program to find the middle node of a singly linked list in Python

PythonServer Side ProgrammingProgramming

Suppose we have a singly linked list node, we have to find the value of the middle node. And when there are two middle nodes, then we will return the second one. We have to try to solve this in single pass.

So, if the input is like [5,9,6,4,8,2,1,4,5,2], then the output will be 2.

To solve this, we will follow these steps−

p:= node
d:= 0, l:= 0
while node is not null, do
- if d is not same as 2, then
  - node:= next of node
  - l := l + 1, d := d + 1
- otherwise,
p:= next of p, d:= 0
- return val of p when l is odd otherwise value of next of p

Let us see the following implementation to get better understanding

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