arcbjorn

thoughtbook

Saturday, March 4, 2023

Leetcode 876 problem.

Go

Slow & fast pointers

• Time complexity: $O(n)$ - n is a length of a list
• Auxiliary space: $O(1)$ - constant amount of space
/**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/

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

return slow
}

Typescript

/**
* 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 {
}

let length = 0;

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

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[] = [];

}

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 {