Middle Element of Linked List Editorial

Practice Problem Link: Middle Element of Linked List

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a linked list, find the middle element and print its value.

If the list has even number of elements, print the first of the two middle elements

Approach

Traverse the whole linked list and count the number of elements. Now, again traverse the linked list up to the middle element.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the ListNode class definition

class ListNode {
public:
	int data;
	ListNode* next;

	ListNode(int data) {
		this->data = data;
		this->next = NULL;
	}
};
*/

int getMiddleElementOfLinkedList (ListNode* list) {
    int listSize = 0;
	ListNode *currentNode = list;
	while(currentNode != NULL) {
		listSize++;
		currentNode = currentNode->next;
	}
	int mid = listSize/2;
	if(listSize % 2 == 0) {
		mid--;
	}
	currentNode = list;
	int i = 0;
	while(i != mid) {
		i++;
		currentNode = currentNode->next;
	}
	return currentNode->data;
}

Java

/** This is the ListNode class definition

class ListNode {
	int data;
	ListNode next;

	ListNode(int data) {
		this.data = data;
		this.next = null;
	}
}
**/

class Solution {
	int getMiddleElementOfLinkedList (ListNode list) {
	    int listSize = 0;
		ListNode currentNode = list;
		while(currentNode != null) {
			listSize++;
			currentNode = currentNode.next;
		}
		int mid = listSize/2;
		if(listSize % 2 == 0) {
			mid--;
		}
		currentNode = list;
		int i = 0;
		while(i != mid) {
			i++;
			currentNode = currentNode.next;
		}
		return currentNode.data;
	}
}

Another Approach

Initialize two pointers say slow and fast pointing to the start of the list.  Move the fast pointer by two nodes and the slow pointer by one node. When the fast pointer reaches the end of the list, the slow pointer must be pointing at the middle node of the list.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the ListNode class definition

class ListNode {
public:
	int data;
	ListNode* next;

	ListNode(int data) {
		this->data = data;
		this->next = NULL;
	}
};
*/

int getMiddleElementOfLinkedList (ListNode* list) {
    ListNode* slow = list;
	ListNode* fast = list;
	while (true) {
		if (fast->next == NULL || fast->next->next == NULL) {
			break;
		}
		slow = slow->next;
		fast = fast->next->next;
	}
	return (slow->data);
}

Java

class Solution {
	int getMiddleElementOfLinkedList (ListNode list) {
		ListNode slow = list;
		ListNode fast = list;
		while (true) {
			if (fast.next == null || fast.next.next == null) {
				break;
			}
			slow = slow.next;
			fast = fast.next.next;
		}
		return (slow.data);
	}
}