find the median of all nodes in a linked list in typescript

To find the median of all nodes in a linked list, we need to follow these steps:

1. Traverse the linked list and count the total number of nodes in the list.
2. Find the middle point of the linked list based on the total number of nodes.
3. Traverse the linked list again and stop at the middle point found in step 2.
4. If the total number of nodes is odd, the value at the middle node is the median. If the total number of nodes is even, the median is the average of the values at the middle two nodes.

Here's the TypeScript code for finding the median of all nodes in a linked list:

index.ts
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);
  }
}

function findMedian(head: ListNode | null): number {
  // First, count the total number of nodes in the linked list
  let count = 0;
  let p = head;
  while (p !== null) {
    count++;
    p = p.next;
  }

  // Find the middle node in the linked list
  p = head;
  for (let i = 0; i < Math.floor(count / 2); i++) {
    p = p.next;
  }

  // Determine the median value based on the total number of nodes
  if (count % 2 === 0) {
    return (p.val + p.next.val) / 2;
  } else {
    return p.val;
  }
}
716 chars
32 lines

Here, we define a ListNode class to represent each node in the linked list. The findMedian function takes the head of the linked list as input and returns the median value as output. We traverse the linked list twice, so the time complexity of this algorithm is O(n), where n is the number of nodes in the linked list.