Posted on Apr 20, 2023

Day 7. Singly Linked List

876. Middle of the Linked List

Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

Input: head = [1,2,3,4,5] Output: [3,4,5] Explanation: The middle node of the list is node 3. Input: head = [1,2,3,4,5,6] Output: [4,5,6] Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.

Pseudo Code

something I didn't know was that head.next returns the rest of the values, not the next value.
head = [1,2,3,4,5], head.val = 1, head.next=[2,3,4,5]

var middleNode = function(head) { // check the total length of initial ListNode // middle index is totalLen/2 // get the ListNode from middle to the end // console.log(head, head.val, head.next) // head: val ~ rest // head.val : val only // head.next: rest only (no val included) } var checkLength = function(head) { // init counter // until current value is null OR // until there's no more next, increment the counter // return the counter }

My Attempt

Things about ListNode (different from Array)

You cannot access the length of the entire nodelist, so we need to traverse the entire ListNode and increment the counter
Be mindful about the LinkedList definition given in the problem set
Be mindful of while loop condition(when to stop the counter), especially inside checking the length function.

// Definition for singly-linked list. function ListNode(val, next) { this.val = (val===undefined ? 0 : val) this.next = (next===undefined ? null : next) }

 /** * @param {ListNode} head * @return {ListNode} */ var middleNode = function(head) { let totalLen = checkLength(head); let mid = ~~(totalLen/2); // ~~: same as Math.floor, but efficient let counter = 0; while(counter < mid) { head = head.next; // update to next ListNode counter += 1; } return head; }; var checkLength = function(head) { let counter = 1; // start with 1 because // while loop ends before counting the last element,  // which has null as next while(head.next !== null) { counter += 1; head = head.next; } return counter; }

Improve

So I kind of got caught up with the fact that this is singly linked list and didn't think too much about two pointers theme.
There seems to be much simpler way to solve this.

Array
two pointers: slow and fast