三、链表

1. https://leetcode-cn.com/problems/linked-list-cycle/

时间复杂度：O(n)
思路：快慢指针，快指针每次走两步，慢指针每次走一步，如果相遇代表是环形链表，反之不是。

var hasCycle = function(head) {
    let p1 = head
    let p2 = head
    while(p1 && p2 && p2.next){
        p1 = p1.next
        p2 = p2.next.next
        if(p1 === p2){
            return true
        }
    }
    return false
};

2. https://leetcode-cn.com/problems/swap-nodes-in-pairs/

时间复杂度：O(n)

var swapPairs = function(head) {
    let demmyHead = new ListNode(0)
    demmyHead.next = head
    let temp = demmyHead
    while(temp.next !== null && temp.next.next !==null){
        let node1 = temp.next
        let node2 = temp.next.next
        temp.next = node2
        node1.next = node2.next
        node2.next = node1
        temp = node1
    }
    return demmyHead.next
};

3. https://leetcode-cn.com/problems/reverse-linked-list/

时间复杂度：O(n)
方法1：迭代

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    let cur = head;
    let pre = null;
    while(cur){
        const curNext = cur.next
        cur.next = pre
        pre = cur
        cur = curNext
    }
    return pre
};

方法2：递归

let reverseList = (head) =>{
  let reverse = (pre, cur) => {
    if(!cur) return pre;
    // 保存 next 节点
    let next = cur.next;
    cur.next = pre;
    reverse(cur, next);
  }
  return reverse(null, head);
}

4. https://leetcode-cn.com/problems/merge-two-sorted-lists/

时间复杂度：O(n)
方法1：递归，小的接着大的就行了

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

迭代

var mergeTwoLists = function(l1, l2) {
   let head = new ListNode()
   let cur = head
   while(l1 && l2){
       if(l1.val < l2.val){
           cur.next = l1
           l1 = l1.next
       }else{
           cur.next = l2
           l2 = l2.next
       }
        cur = cur.next
   }
   cur.next = l1!==null?l1:l2
   return head.next
};

5. (203) https://leetcode-cn.com/problems/remove-linked-list-elements/submissions/

时间复杂度：O(n)
创建一个虚拟头节点放在链表最前面，遍历链表，如果当前值等于输入值，则链表跳过当前值，否则继续走。

var removeElements = function(head, val) {
    let dummyHead = new ListNode()
    dummyHead.next = head
    let temp = dummyHead
    while(temp.next !== null){
        if(temp.next.val === val){
            temp.next = temp.next.next
        }else{
            temp = temp.next
        }
    }
    return dummyHead.next 
};

6. (83) https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
const deleteDuplicates = function(head) {
    // 设定 cur 指针，初始位置为链表第一个结点
    let cur = head;
    // 遍历链表
    while(cur != null && cur.next != null) {
        // 若当前结点和它后面一个结点值相等（重复）
        if(cur.val === cur.next.val) {
            // 删除靠后的那个结点（去重）
            cur.next = cur.next.next;
        } else {
            // 若不重复，继续遍历
            cur = cur.next;
        }
    }
    return head;
};

7. (82) https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/

const deleteDuplicates = function(head) {
    // 极端情况：0个或1个结点，则不会重复，直接返回
    if(!head || !head.next) {
        return head
    }
    // dummy 登场
    let dummy = new ListNode() 
    // dummy 永远指向头结点
    dummy.next = head   
    // cur 从 dummy 开始遍历
    let cur = dummy 
    // 当 cur 的后面有至少两个结点时
    while(cur.next && cur.next.next) {
        // 对 cur 后面的两个结点进行比较
        if(cur.next.val === cur.next.next.val) {
            // 若值重复，则记下这个值
            let val = cur.next.val
            // 反复地排查后面的元素是否存在多次重复该值的情况
            while(cur.next && cur.next.val===val) {
                // 若有，则删除
                cur.next = cur.next.next 
            }
        } else {
            // 若不重复，则正常遍历
            cur = cur.next
        }
    }
    // 返回链表的起始结点
    return dummy.next;
};