劍指 Offer 18. 刪除鏈表的節(jié)點(diǎn)

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xz4mp2/
時間復(fù)雜度：O(n)租谈，空間復(fù)雜度：O(1)

var deleteNode = function(head, val) {
    if(head == null){
        return null;
    }
    if(head.val == val){
        return head.next;
    }
    var left = head;
    var cur = left.next
    while(cur.val != val && cur.next!= null){
        left=cur;
        cur=cur.next;
    }
    if(cur != null){
        left.next=cur.next
    }
    return head
};

劍指 Offer 22. 鏈表中倒數(shù)第 k 個節(jié)點(diǎn)

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xzy5ei/
時間復(fù)雜度：O(n)椅挣，空間復(fù)雜度：O(1)

var getKthFromEnd = function(head, k) {
    var cur = head;
    var post= head;
    for(var i=0; i<k; i++){
        cur = cur.next;
    }
    while(cur!=null){
        cur = cur.next;
        post = post.next
    }
    return post
};

劍指 Offer 24. 反轉(zhuǎn)鏈表

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xzccxg/
時間復(fù)雜度：O(n)侥猬，空間復(fù)雜度：O(1)

var reverseList = function(head) {
    var cur = null;
    var pre = head;
    while(pre!=null){
       var tmp = pre.next;
        pre.next = cur;
        cur = pre;
        pre = tmp;
    }
    return cur
};

劍指 Offer 25. 合并兩個排序的鏈表

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xzjkjj/
輸入兩個遞增排序的鏈表榨了，合并這兩個鏈表并使新鏈表中的節(jié)點(diǎn)仍然是遞增排序的识颊。O(m+n)

var mergeTwoLists = function(l1, l2) {
    if(l2==null){
        return l1
  }
    if(l1==null){
        return l2
  }
    if(l1.val>l2.val){
        l2.next = mergeTwoLists(l1,l2.next);
        return l2
    }else{
        l1.next = mergeTwoLists(l2,l1.next);
        return l1
    }
};

劍指 Offer 52. 兩個鏈表的第一個公共節(jié)點(diǎn)

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xshucr/
使用兩個指針 node1杂拨，node2 分別指向兩個鏈表 headA锡凝，headB 的頭結(jié)點(diǎn)杉女，然后同時分別逐結(jié)點(diǎn)遍歷贰剥，
當(dāng) node1 到達(dá)鏈表 headA 的末尾時头谜，重新定位到鏈表 headB 的頭結(jié)點(diǎn)；
當(dāng) node2 到達(dá)鏈表 headB 的末尾時鸠澈，重新定位到鏈表 headA 的頭結(jié)點(diǎn)柱告。
這樣，當(dāng)它們相遇時笑陈，所指向的結(jié)點(diǎn)就是第一個公共結(jié)點(diǎn)际度。

• 時間復(fù)雜度：O(M+N)。
• 空間復(fù)雜度：O(1)O(1)涵妥。

//（雙指針法）
var getIntersectionNode = function(headA, headB) {
    let curA = headA;
    let curB = headB;
    while (curA != curB) {
        curA = curA != null ? curA.next : headB;
        curB = curB != null ? curB.next : headA;
    }
    return curA;
};