1. Merge two ordered lists

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    var dumpy = new ListNode();
    var p = dumpy;
    while(l1&&l2) {
        if(l1.val<l2.val){
            p.next = l1;
            l1 = l1.next;
        } else {
            p.next = l2;
            l2 = l2.next;
        }
        p = p.next;
    }
    if(l1){
        p.next = l1;
    }
    if(l2){
        p.next = l2;
    }
    return dumpy.next;
};
Copy the code

2. The penultimate KTH node in the linked list

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var getKthFromEnd = function(head, k) {
   var fast = head;
   var slow = head;
   var i=1;
   while(i<=k){
       fast = fast.next;
       i++
   }
   while(fast){
       fast = fast.next;
       slow = slow.next;
   }
   return slow;
};
Copy the code

3. The first common node of two linked lists

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} headA * @param {ListNode} headB * @return {ListNode} */ var getIntersectionNode = function(headA, headB) { var lenA = getLen(headA); var lenB = getLen(headB) while(lenA! =lenB){ if(lenA>lenB){ headA = headA.next; lenA--; }else { headB = headB.next; lenB--; } } while(headB! =headA){ headA = headA.next; headB = headB.next; } return headA; } var getLen = function(node){ var temp = node; var i=0; while(temp){ temp = temp.next; i++; } return i; }Copy the code

4. Chain list inversion

/**
 * 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 reverseList = function(head) {

    var pre = null;
    var cur = head;
    while(cur){
        var temp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = temp;
    }
    return pre;
};
Copy the code

5. Circular lists and their rings

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; @param {ListNode} head * @return {ListNode} */ var detectCycle = function(head) =new Set(); // var temp = head; // while(temp){ // if(contains.has(temp)){ // return temp; // } // contains.add(temp); // temp = temp.next; // } // return null if(head==null){ return null; } var fast = head; var slow = head; var ptr = head; while(fast){ if(fast.next==null){ return null; } fast = fast.next.next; slow = slow.next; if(fast==slow){ while(ptr! =slow){ ptr = ptr.next; slow = slow.next; } return ptr; } } return null; };Copy the code

6. Reverse linked list II

/** * 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) { var dumpy = new ListNode(); dumpy.next = head; var pre = dumpy; var i=1; while(pre&&i<left){ pre = pre.next; i++; } var rightNode = pre.next; var j=1; while(rightNode&&j<(right-left+1)){ rightNode = rightNode.next; j++; } var leftNode = pre.next; var temp = rightNode.next; pre.next = null; rightNode.next = null; pre.next = reverse(leftNode); leftNode.next = temp; return dumpy.next; }; var reverse = function(root) { if(! root) { return root; } var cur = root; var pre = null; while(cur){ var temp = cur.next; cur.next = pre; pre = cur; cur = temp; } return pre; }Copy the code

Delete the NTH node from the 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} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
   var fast = head;
   var dumpy = new ListNode();
   dumpy.next = head;
   var slow = dumpy;
   var i=1;
   while(fast&&i<=n){
       fast = fast.next;
       i++;
   }
   while(fast){
       slow = slow.next;
       fast = fast.next;
   }
   slow.next = slow.next.next;
   return dumpy.next;
};
Copy the code

8. Sum of two 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} l1 * @param {ListNode} l2 * @return {ListNode} */ var addTwoNumbers = function(l1, l2) { var dumpy = new ListNode(); var temp = dumpy; var extra = 0; while(l1||l2){ var n1 = l1! =null? l1.val:0; var n2 = l2! =null? l2.val:0; var sum = n1+n2+extra; extra = Math.floor(sum/10); temp.next = new ListNode(sum%10); temp = temp.next if(l1){ l1 = l1.next; } if(l2){ l2 = l2.next; } } if(extra){ temp.next = new ListNode(extra); } return dumpy.next; };Copy the code

9. Merge K ascending lists

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode[]} lists * @return {ListNode} */ var mergeKLists = function(lists) { if(lists.length==0){ return null; } var temp = lists[0]; for(var i=1; i<lists.length; i++){ temp = mergeLinkTwo(temp,lists[i]) } return temp; }; var mergeLinkTwo = function(l1,l2){ var dumpy = new ListNode(); var ptr = dumpy; while(l1&&l2){ if(l1.val<l2.val){ ptr.next = l1; l1 = l1.next; } else { ptr.next = l2; l2 = l2.next; } ptr = ptr.next; } if(l1){ ptr.next = l1; } if(l2){ ptr.next = l2; } return dumpy.next; }Copy the code

10. Sort linked lists (merge)

/** * 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 sortList = function(head) { if(! head||head.next==null){ return head; } var fast = head; var slow = head; while(fast&&fast.next&&fast.next.next){ fast = fast.next.next; slow = slow.next; } var right = sortList(slow.next); slow.next = null; var left = sortList(head); return mergLink(left,right) }; var mergLink = function(l1,l2){ var dumpy = new ListNode(); var ptr = dumpy; while(l1&&l2){ if(l1.val<l2.val){ ptr.next = l1; l1 = l1.next; } else { ptr.next = l2; l2 = l2.next; } ptr = ptr.next; } if(l1){ ptr.next = l1; } if(l2){ ptr.next = l2; } return dumpy.next; }Copy the code

11. Flip linked lists in groups of K

/** * 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) { var dumpy = new ListNode(); dumpy.next = head; var pre = dumpy; var rightNode = dumpy; while(rightNode){ var i=0; while(rightNode&&i<k){ rightNode = rightNode.next; i++; } if(rightNode){ var temp = rightNode.next; var leftNode = pre.next; rightNode.next = null; pre.next = reverse(leftNode); leftNode.next = temp; pre = leftNode; rightNode = leftNode } } return dumpy.next; }; var reverse = function(root){ if(! root){ return root; } var pre = null; var cur = root; while(cur){ var temp = cur.next; cur.next = pre; pre = cur; cur = temp; } return pre; }Copy the code