Middle of the linked list

Go

Slow & fast pointers

Time complexity: $O(n)$ - n is a length of a list
Auxiliary space: $O(1)$ - constant amount of space

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

    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    
    return slow
}

Typescript

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

Counting method

Time complexity: $O(n)$ - n is a length of a list
Auxiliary space: $O(1)$ - constant amount of space

function middleNode(head: ListNode | null): ListNode | null {
    if (!head.next) {
        return head;
    }

    let length = 0;
    let current = head;

    while (current) {
        current = current.next;
        length++;
    }

    current = head;

    for (let i = 0 ; i < Math.floor(length/2) ; i++){
        current = current.next; 
    }

    return current;
};

Array

Time complexity: $O(n)$ - n is a length of a list
Auxiliary space: $O(n)$ - n is a length of a list

function middleNode(head: ListNode | null): ListNode | null {
  const nodes: ListNode[] = [];
  
  while (head != null) {
      nodes.push(head);
      head = head.next;
  }
  
  const midIndex = Math.floor(nodes.length / 2);
  
  return nodes[midIndex];
};

Slow & fast pointers

Time complexity: $O(n)$ - n is a length of a list
Auxiliary space: $O(1)$ - constant amount of space

function middleNode(head: ListNode | null): ListNode | null {
  let slow = head;
  let fast = head;
  
  while (fast && fast.next){
    slow = slow.next;
    fast = fast.next.next;
  }
  
  return slow;
};

thoughtbook

Middle of the linked list

Go

Slow & fast pointers

Typescript

Counting method

Array

Slow & fast pointers