# 链表相关的操作

## 链表是否有环

```js
// 判断是否有环,有返回入口节点,无返回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 不能序列化含有循环引用的结构

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

```

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

```js
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
};
```

## 链表反转（反转链表）

```js
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 个节点

```js
/**
 * 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

```js
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
    }
}


```

## 两两交换链表中的节点

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

```js
/**
 * 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 的链表

```js
/**
 * 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 即可。

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://shenjunhong.gitbook.io/blog/yuan-ma/yuan-ma-shou-xie-xi-lie/shou-xie-lian-biao.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.