83. Delete duplicate elements from sorted linked lists

Their thinking

  • Define two adjacent Pointers pre and cur
  • Each pointer moves back one bit to determine the value of the two nodes
  • If they are not equal, move them back one bit at the same time
  • If equal, the cur pointer is moved back one bit, and the pre node next points to the new cur node
/** * 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) {
    if(! head || ! head.next) {return head;
    }
    let pre = head;
    let cur = head.next;
    while(cur) {
        if(cur.val === pre.val) {
            cur = cur.next;
            pre.next = cur;
        } else{ cur = cur.next; pre = pre.next; }}return head;
};
Copy the code

61. Rotate linked lists

Their thinking
  • Join the end node of the list to the end node to form a ring
  • Finds the previous node of the rotated list head node
  • Unloop to return the new head node
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
 * @param {number} k
 * @return {ListNode}* /
var rotateRight = function(head, k) {
 if(! head || ! head.next) {return head;
  }
  let tail = head;
  let len = 1;
  // Find the last node in the list and point tail's next to head
  while (tail.next) {
    tail = tail.next;
    len++;
  }
  // Tail points to the last node, and the next attribute points to head
  tail.next = head;
 // Convert a right-handed rotation to a left-handed rotation
  let n = len - (k % len);
  let pre = head;
  let ret = head;

  // user -- there is one less rotation for easy operation
  while (--n) {
    pre = pre.next;
  }
  // ret points to the new head node
  ret = pre.next;
  // Disassemble the ring
  pre.next = null;
  return ret;
};
Copy the code

92. Reverse linked list II

Their thinking
  • Find the node before the head node that you want to flip
  • Reverve function: Flipping the k nodes starting with the first node returns a new list containing the unflipped portion
  • Link the first half and part of the new 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
 * @param {number} left
 * @param {number} right
 * @return {ListNode}* /
var reverseBetween = function(head, left, right) {
    if(! head || ! head.next) {return head;
    }
    if(right -left ===0) {
        return head;
    }
    // Virtual head node
    const ret = new ListNode(null,head);

    // Find the previous node of left
    let l = left;
    let pre = ret;
    while(--l) {
        pre = pre.next;
    }

    const reserve = (head,n) = > {
        if(! head) {return null;
        }
        let pre = null;
        let cur = head;
        // Reverse the first k nodes
        while(cur && n-- > 0) {
            const next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        // head: flip the tail node of the part, pre: flip the head node of the part
        // cur: the head node of the rest
        head.next = cur;
        return pre;
    }
    // The pre is the previous node that needs to be flipped
    // Reserve returns the next part of the list, and the left to right part has been flipped
    pre.next = reserve(pre.next,right - left + 1);
    return ret.next;
};
Copy the code

Delete the NTH node from the list

Their thinking

How do I find the NTH to last node

  • Define the first pointer front, go back n steps,
  • Define the second pointer after, where front and after go backwards together
  • When front goes to the end of the list, after points to the NTH node from the bottom

Tip: When there is a high probability that the node will change, the trick of using the virtual head node is to define a virtual list node in the head with the next pointer pointing to the head

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
 * @param {number} n
 * @return {ListNode}* /
var removeNthFromEnd = function(head, n) {
      if(! head) {return null;
  }
  // Define the virtual head node
  let ret = new ListNode(null, head);
  let front = ret;
  while (n--) {
    front = front.next;
  }

  // Define the after pointer, and then both Pointers go backwards together
  let after = ret;
  while (front.next) {
    after = after.next;
    front = front.next;
  }
  // after points to the previous node of the penultimate node
  after.next = after.next.next;
  return ret.next;
};
Copy the code