arcbjorn

thoughtbook

RSS Feed

Saturday, March 4, 2023

Middle of the linked list

Leetcode 876 problem.

Go

Slow & fast pointers

  • Time complexity: O(n)O(n) - n is a length of a list
  • Auxiliary space: O(1)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)O(n) - n is a length of a list
  • Auxiliary space: O(1)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)O(n) - n is a length of a list
  • Auxiliary space: O(n)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)O(n) - n is a length of a list
  • Auxiliary space: O(1)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;
};
Creative Commons Licence