Middle of the Linked List

This is an easy problem from LeetCode (Problem #876).

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

Input: head = [1,2,3,4,5]

Output: [3,4,5]

Example 2

Input: head = [1,2,3,4,5,6]

Output: [4,5,6]

Solution 1

We simply count the number of nodes in the linked list by traversing it. If there are $n$ nodes, then we are interested in the node indexed by n//2 + 1. We start the traversal again from the head until we reach target. We stop at target and return the node.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        counter = 1
        node = head
        while node.next != None:
            node = node.next
            counter += 1
            
        target = counter//2 +1
        
        node = head
        counter = 1
        while counter < target:
            node = node.next
            counter += 1
        return node

Runtime:

The time complexity is $O(n)$ as we always travel $3n/2$ nodes. Since we are not using any additional data structures, the space complexity is $O(1)$.

Solution 2

We could use two pointers, namely, fast and slower pointers, to traverse the linked list. The slow pointer advances one node at a time, while the fast pointer advances two nodes at a time. This means, when the fast pointer reaches the end of the linked list, the slower pointer is guaranteed to be at the middle of the list. We just return the node where the slower pointer is pointing to at that time.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slowPtr = fastPtr = head
        while fastPtr and fastPtr.next:
            slowPtr = slowPtr.next
            fastPtr = fastPtr.next.next
        return slowPtr

Runtime:

The time complexity is $O(n)$ as we always travel $n$ nodes(the fastPtr traverses $n/2$ nodes and the slowPtr traverses $n/2$ nodes). Since we are not using any additional data structures, the space complexity is $O(1)$.

Back to Queues Problems

Anusha Murali

Middle of the Linked List

anusha-murali.github.io