链表相关的操作

链表是否有环

// 判断是否有环,有返回入口节点,无返回null·

let hasCycle = function(head) {
	let set = new Set();
	while (head != null) {
		if (set.has(head)) {
			return head;
		} else {
			set.add(head)
			head = head.next;
		}
	}
	return null;
};

利用 json.stringify 不能序列化含有循环引用的结构

let hasCycle = function(head) {
    try{
        JSON.stringify(head);
        return false;
    }
    catch(err){
        return true;
    }
};

解法三：快慢指针（双指针法） 设置快慢两个指针，遍历单链表，快指针一次走两步，慢指针一次走一步，如果单链表中存在环，则快慢指针终会指向同一个节点，否则直到快指针指向 null 时，快慢指针都不可能相遇

let hasCycle = function(head) {
    if(!head || !head.next) {
        return false
    }
    let fast = head.next.next, slow = head.next
    while(fast !== slow) {
        if(!fast || !fast.next) return false
        fast = fast.next.next
        slow = slow.next
    }
    return true
};

链表反转（反转链表）

function reverse(head){
  if(!head || !head.next) return head;
  var prev = null, cur = head;

  while(cur){
    // 用于临时存储 cur 后继节点

    var next = curr.next;

    // 反转 cur 的后继指针

    cur.next = prev;

    // 变更 prev, cur
    prev = cur
    cur = next
  }

  return prev
}

链表倒数第 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) {
    let fast = head
    let slow = head
    let i = 0
    while(i++ < k) {
        fast = fast.next
    }

    while(fast) {
        fast = fast.next
        slow = slow.next
    }

    return slow
};

合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4

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

两两交换链表中的节点

递归的终止条件是链表中没有节点，或者链表中只有一个节点，此时无法进行交换。

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

    if (head === null || head.next === null) {
        return head;
    }
    const newHead = head.next;
    head.next = swapPairs(newHead.next);
    newHead.next = head;
    return newHead;
};

这边其实分为三个步骤

1. 首先判断 head 有没有 和 head。next 有没有存在

2. 原始链表的头节点是 newHead 表示新的链表的头节点， 原始链表的第二个节点， 则原始链表的其余节点的头节点是 newHead.next。 令head.next = swapPairs(newHead.next)， 表示将其余节点进行两两交换， 交换后的新的节点为head的下一个节点，

3. 然后令 newHead.next = head，即可完成所有节点的交换。 最后返回新的链表的头节点 newHead。

反转从位置 m 到 n 的链表

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} m
 * @param {number} n
 * @return {ListNode}
 */
var reverseBetween = function(head, m, n) {
    // 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论

    var dummy = new ListNode(-1)
    dummy.next = head
    var prev = dummy
    //第一步：从虚拟头节点走 m-1 步，来到第 m 个节点的前一个节点
    var cur = head
    var reverse = null
    var reverseLastNode = null
    var index = 1

    while(index <= n) {
        if(index < m) {
            prev = prev.next;
            cur = cur.next;
        } else {
            // 反转前的第一个节点，也就是反转后的最后一个节点
            if(reverseLastNode === null) {
                reverseLastNode = cur;
            }
            // 交换
            var temp = reverse;
            reverse = cur;
            cur = cur.next;
            reverse.next = temp;
        }
        index++;
    }

    prev.next = reverse;
    reverseLastNode.next = cur;

    return dummy.next
};

/*输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
*/

删除中间节点

但是本题中我们只能访问要删除的节点，所以这个方法用不了。那我们可以把当前节点的下一个节点的值拿过来覆盖掉要删除的值，然后把当前节点的 next 指向下一个节点的 next 即可。

var deleteNode = function(node){
  node.val = node.next.val;
  node.next = node.next.next;
}