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)

1. You cannot access the length of the entire nodelist, so we need to traverse the entire ListNode and increment the counter
2. Be mindful about the LinkedList definition given in the problem set
3. 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.

1. Array

2. two pointers: slow and fast

Relevant problem sets

2095. Delete the Middle Node of a Linked List
2130. Maximum Twin Sum of a Linked List