83. Delete duplicate elements from sorted linked lists

Their thinking
  • Because lists are ordered, repeating elements are adjacent
  • Iterate through the list and delete the next element if it finds that the current element has the same value as the next
  • Iterate through the list and delete the value of the next element if the current element is found to have the same value as the next element
  • At the end of the traversal, return the head of the original list
/** * 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 deleteDuplicates = function(head) {
    let p1 = head
    while(p1 && p1.next) {

        if(p1.val === p1.next.val) {
            p1.next = p1.next.next
        }else{ p1 = p1.next; }}return head;
};
Copy the code

141. Circular linked lists

Their thinking
  • Two people start at the same time from the starting point of the circular playground, and the fast one is sure to pass the slow one lap
  • Use two Pointers, one fast and one slow, to traverse the list. If Pointers can meet, the list has a ring
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /

/ * * *@param {ListNode} head
 * @return {boolean}* /
var hasCycle = function(head) {
    // Remove the empty list
    if(! head) {return false};
    let p1 = head;
    let p2 = head;
    // use p2 for non-null judgment
    while(p2.next ! = =null&& p2.next.next ! = =null) {
        p1 = p1.next;
        p2 = p2.next.next;
        if(p1 === p2) {
            return true; }}return false;
};
Copy the code

102. Sequence traversal of binary trees

Their thinking
  • Sequence traversal is breadth-first traversal
  • The hierarchy of the current node needs to be recorded during traversal so that it can be added to different arrays
  • Breadth-first traversal of a binary tree
  • As you traverse, you record the hierarchy of each node and add it to a different array
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
 * @return {number[][]}* /
var levelOrder = function(root) {
        // Store hierarchical data
        let res = [];
        // Null returns directly
        if(! root){return []}
        // add headers to queue [value, hierarchy]
        const queue = [[root,0]].while(queue? .length) {const [c,l] = queue.shift();
            // Add the corresponding level of 2d datares[l] ? res[l].push(c.val) : res[l] = [c.val] ; c? .left && queue.push([c.left,l +1]); c? .right && queue.push([c.right, l +1]); 
        }
    return res;
};
Copy the code

Middle order traversal of binary trees

Their thinking
  • Middle order traversal (recursive and non-recursive)
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
 * @return {number[]}* /
var inorderTraversal = function(root) {
    /** // const res =[]; const rec = (n) => { if(! n) { return null} n.left && rec(n.left); res.push(n.val) n.right && rec(n.right) } rec(root) return res; * * /
    const res =[];
    const stack = [];
    let p = root;
    while(stack.length || p) {
     while(p) {
        stack.push(p)
        p = p.left;
     }
     // Access the left node
     const n = stack.pop();
     res.push(n.val)
     // Point the pointer to the right node
     p = n.right
    }
    return res;
};
Copy the code