刷题6 剑指 Offer — 链表

剑指 Offer 18. 删除链表的节点

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xz4mp2/
时间复杂度：O(n)，空间复杂度：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. 链表中倒数第 k 个节点

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xzy5ei/
时间复杂度：O(n)，空间复杂度：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. 反转链表

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xzccxg/
时间复杂度：O(n)，空间复杂度：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/
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。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. 两个链表的第一个公共节点

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xshucr/
使用两个指针 node1，node2 分别指向两个链表 headA，headB 的头结点，然后同时分别逐结点遍历，
当 node1 到达链表 headA 的末尾时，重新定位到链表 headB 的头结点；
当 node2 到达链表 headB 的末尾时，重新定位到链表 headA 的头结点。
这样，当它们相遇时，所指向的结点就是第一个公共结点。

• 时间复杂度：O(M+N)。
• 空间复杂度：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;
};