Problem

Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

Example 1:

graph LR
    1 --> 2 --> 3:::RedNode --> 4 --> 5

classDef RedNode fill:#ff0000;
  
1
2
3
4
5

Input:
head = [1,2,3,4,5]
Output:
 [3,4,5]
Explanation: The middle node of the list is node 3.

Example 2:

graph LR
    1 --> 2 --> 3 --> 4:::RedNode --> 5 --> 6

classDef RedNode fill:#ff0000;
  
1
2
3
4
5

Input:
head = [1,2,3,4,5,6]
Output:
 [4,5,6]
Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.

Follow up

Follow up - How will you get it in first pass.

Solution

Method 1 - Get the Length and Travel to Middle

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.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

public ListNode getMiddleNode(ListNode head) {
	// initialize current pointer to head of the linked list
	ListNode current = head;
	int n = 0;
	while(current!= null){
		n++;
		current = current.next;
	}

	current = head;

	for(int i=0;i<n/2;i++){
		current = current.next;
	}
	return current;
}

Complexity

  • ⏰ Time complexity: O(n), where n is length of linked list.
  • 🧺 Space complexity: O(1)

Method 2 - Uses One Slow Pointer and One Fast Pointer 🏆

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. This is done in single pass.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

public ListNode middleNode(ListNode head) {
	ListNode fast = head, slow = head;

	while (fast != null && fast.next != null) {
		fast = fast.next.next;
		slow = slow.next;
	}

	return slow;
}

Method 3 - Using a Counter

Initialize mid element as head and initialize a counter as 0. Traverse the list from head, while traversing increment the counter and change mid to mid->next whenever the counter is odd. So the mid will move only half of the total length of the list.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

mynode * getTheMiddle(mynode * head) {
	mynode * middle = (mynode * ) NULL;
	int i;

	for (i = 1; head != (mynode * ) NULL; head = head -> next, i++) {
		if (i == 1)
			middle = head;
		else if ((i % 2) == 1)
			middle = middle -> next;
	}

	return middle;
}