# Finding middle element in a linked list

## Let’s understand the problem!

Write a programme that discover the middle node of a singly linked list given a single node. If the number of nodes is even, we must return the second middle node.

Examples

Input: 5->4->3->2->1, Output: 3

Explanation: Because there are five nodes in this diagram, there is one centre node, which is 3.

Input: 6->5->4->3->2->1, Output: 3

Explanation: There are six nodes, with the first middle node being four and the second middle node being three. As a result, we must return the pointer to node value 3.

## Approaches to solving the problem were discussed

• Using more RAM, a brute force strategy is used.
• Double traversal of the linked list by counting nodes
• Counting nodes: traversal of the linked list in a single step
• Using slow and fast pointers, an effective solution was found.

## A brute force approach  using extra memory

The main idea is to keep each linked list node (in the same order) in an extra array with a size equal to the linked list’s length, and then access the middle node by accessing the array’s middle index.

Solution Pseudocode

```ListNode getMiddleNode(ListNode head)

{

ListNode temp[length]

int count = 0

{

count = count + 1

}

return temp[count/2]

}
```

## Analysis of time and spatial complexity

Suppose the length of the linked list is n. So the time complexity = Time complexity of finding the length of linked list + Time complexity of storing nodes into extra memory = O(n) + O(n) = O(n)

For storing nodes in an n-size array, the space complexity is O(n).

## Double traversal of the linked list by counting nodes

### Solution Idea

We’re using additional space to discover the centre node of the linked list in the way above. The key challenge now is if we can reduce space complexity to O(1).

One possibility is to count the number of nodes in the linked list before traversing it count/2 times. So we’ll be at the middle node at the conclusion of the second traverse.

### Steps to a Solution

• The variable count is set to 0 by default.
• We also create a list pointer middle to keep track of the middle node, which is set to head.
• Now we count the number of nodes in a loop till head!= NULL.
• Now we run another loop till I n/2 and increment the middle pointer value in each iteration.
• We return the middle pointer at the end of the second loop.

### Solution Pseudocode

```ListNode getMiddleNode(ListNode head)

{

int count = 0

{

count = count + 1

}

int i = 0

while (i < count/2)

{

middle = middle->next

i = i + 1

}

return middle

}
```

### Time and space complexity analysis

Suppose the length of the linked list is n. So the time complexity = Time complexity of finding the node count + Time complexity of finding the middle node = O(n) + O(n) = O(n)

Space complexity = O(1), as we are using constant extra space.

## Counting nodes: traversal of the linked list in a single step

Another idea: in a single traversal, we can track both the number of nodes and the middle node.

• To keep track of the number of nodes, we create a variable count.
• We also create a pointer middle to keep track of the middle node.
• We’ll now run a loop until head!= NULL.
• The count value is increased by one at each repetition. We increase the centre pointer by one when the count value is even.
• The middle pointer will be at the middle node by the end of the loop, and we will return this value.

### Solution Pseudocode

```ListNode getMiddleNode(ListNode head)

{

int count = 0

{

if (count % 2 == 0)

middle = middle->next

count = count + 1