链表专题

1.合并两个有序链表

/**
 * 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;
};
复制代码

2.链表中倒数第k个节点

/**
 * 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;
};
复制代码

3.两个链表的第一个公共节点

/**
 * 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;
}
复制代码

4.链表倒置

/**
 * 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;
};
复制代码

5.环形链表及其环

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    //set集合法
    // var contains =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;
};
复制代码