202. Happiness

Their thinking
  • Convert to whether the linked list has a ring problem
  • If you have a ring, it’s not a happy number
  • If it equals 1, it’s the happiness number
/ * * *@param {number} n
 * @return {boolean}* /
var isHappy = function(n) {
    
    const getNext = (num) = > {
        let result = 0;
        while(num) {
            // The sum of the squares of the units digit
            result += (num%10) * (num%10);
            num = Math.floor(num/10);
        }
        return result;
    }

    let pre = n;
    let cur = getNext(n);
    while(cur ! = =1) {
        pre = getNext(pre);
        cur = getNext(getNext(cur));
        if(pre === cur) {
            return false; }}return true;
};
Copy the code

Delete duplicate element II from sorted list

Their thinking

  • Use two Pointers, pre, cur
  • Determine whether pre. Next. Val is equal to cur.next
  • Equal cur continues to move forward until unequal
  • Point pre-next and cur to cur.next
/** * 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) {return null;
    }
    const ret = new ListNode(null,head);

    let pre = ret;
    let cur = head;
    while(cur && cur.next) {
        // Determine in advance whether the next pointer node value is equal
        if(pre.next.val ! == cur.next.val) { pre = pre.next; cur = cur.next; }else {
            // If equal cur continues to move forward
            while(cur && cur.next && pre.next.val === cur.next.val) { cur = cur.next; } pre.next = cur.next; cur = cur.next; }}return ret.next;
};
Copy the code

25. Flip linked lists in groups of K

Their thinking
  • Reuse flipped list idea #### 92. Flipped list II
  • Add less than k and do not reverse the logic
/** * 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 reverseKGroup = function(head, k) {
    if(! head) {return null;
    }
     const reserve = (head,n) = > {
        if(! head) {return null;
        }
        let pre = head;
        let cur = head;
        let con = n;
        // Check whether n nodes are sufficient
        while(--n && pre) {
            pre = pre.next;
        }
        if(! pre) {return head;
        }
        pre = null;
        // Reverse the first k nodes
        while(cur && con-- > 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;
    }
    let ret = new ListNode(null, head);
    let pre = ret;
    while(true) {
        pre.next = reserve(pre.next,k);
        for(let i=0; i < k && pre; i++) { pre = pre.next; }if(! pre) {break; }}return ret.next;
};
Copy the code

86. Separate linked lists

/** * 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} x
 * @return {ListNode}* /
var partition = function(head, x) {
    if(! head || ! head.next) {return head;
    }
    const minHead = new ListNode(null);
    const maxHead = new ListNode(null);

    let cur = head;
    let min = minHead;
    let max = maxHead;

    while(cur) {
        if(cur.val < x) {
            min.next = new ListNode(cur.val);
            min = min.next;
        } else {
            max.next =  new ListNode(cur.val);
            max = max.next;
        }
        cur = cur.next;
    }
   // min.next The tail of the small list
   // maxHead is the large list head
   // Next points the head of the big list to the end of the small list
    min.next = maxHead.next;
    // Return the small list
    return minHead.next;
};
Copy the code
Method 2
/** * 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} x
 * @return {ListNode}* /
var partition = function(head, x) {
    if(! head || ! head.next) {return head;
    }
    const minHead = new ListNode(null);
    const maxHead = new ListNode(null);

    let cur = head;
    let min = minHead;
    let max = maxHead;

    while(cur) {
        if(cur.val < x) {
            min.next = cur;
            min = cur;
        } else {
            max.next =  cur;
            max = cur;
        }
        cur = cur.next;
    }
   // min.next The tail of the small list
   // maxHead is the large list head
   // Next points the head of the big list to the end of the small list
    min.next = maxHead.next;
    max.next = null;
    // Return the small list
    return minHead.next;
};
Copy the code