876. Middle of the Linked List

Solution to problem 876 “Middle of the Linked List” from LeetCode.

Problem Statement

Given a non-empty, singly-linked list with head node head, return a pointer to the node located in the middle of the list. If the middle falls on 2 nodes - the second one should be returned

Example 1

Input: [1,2,3,4,5]
Output: Node 3 from this list (Serialization: [3,4,5])

Example 2

Input: [1,2,3,4,5,6]
Output: Node 4 from this list (Serialization: [4,5,6])

Constraints

• Number of nodes from 1 to 100

Solution

Length counting with double traversal

Algorithm idea:

First pass through the list to count the length of the list

Calculate the index of the middle element

Go through the list a second time to the middle element (we know its index). Return this element

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func middleNode(head *ListNode) *ListNode {
    l := 0

    cur := head
    for cur != nil {
        l++
        cur = cur.Next
    }
      middle := l/2

    cur = head
    for idx :=0; idx<middle;idx++{
        cur = cur.Next
    }

    return cur

}

Slow and Fast Pointer

Algorithm idea:

Create two pointers. The slow one will move to the next element The fast one - through an element

As soon as the fast one reaches the end of the list – the slow one will point to the middle.

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func middleNode(head *ListNode) *ListNode {
    slow := head
    fast := head

    for (fast != nil && fast.Next != nil) {
        slow = slow.Next
        fast = fast.Next.Next
    }

    return slow

}