刷完这篇文章，再也不怕链表啦！

寻找单链表的倒数第 k 个节点

双指针，先让两个指针之间的距离保持在k。 当右边指针到达最后一个节点，左边指针所指向的就是倒数第k+1个节点。

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

删除链表的倒数第 N 个结点

根据上一题的解法，寻找倒数第N个结点。
假设该节点为x节点，则将x-1节点 指向 x+1 节点。因此还需要维护一个 pre 节点。
如果链表只有一个节点，则x-1节点不存在，要另外讨论。
为了不另外讨论，可以在链表前添加一个哨兵结点。

/* @param {ListNode} head* @param {number} n* @return {ListNode}*/
var removeNthFromEnd = function(head, n) {// 用一个哨兵节点，防止需要另外处理只有一个节点的特殊链表。let dummy = new ListNode(-1);dummy.next = head;let left = head;let pre = dummy;let right = head;for(let i = 0;i<n;i++){right = right.next}while(right!=null){right = right.next;left = left.next;pre = pre.next;}pre.next = left.next;return dummy.next
};

旋转链表

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

思路：利用指针的移动，形成闭环。并且记录长度,找到该断开的地方断开。

向右移动k位，则说明前面增加k个结点，说明最后k个结点需要在首位。因此在第（len-k）个结点处需要断裂。

其实就是找到倒数第k个结点，让它与倒数第k+1个结点之间断开。由于k 有可能大于长度，因此需要提前计算出链表的长度。

var rotateRight = function(head, k) {if(head==null)return nulllet left = head;let right = head;let len = 0;while(right!=null){len++;right = right.next;}k = k%len;right = head;for(let i = 0;i<k;i++){right = right.next;}while(right.next!=null){right = right.next;left = left.next;}right.next = head;let res = left.next;left.next = null;return res;};

public ListNode rotateRight(ListNode head, int k) {ListNode tail = head;ListNode pre = head;if(head==null)return null;int len=1;while(tail.next!=null){tail = tail.next;len++;// System.out.println(len);}tail.next=head;k=k%len;for (int i = 0; i < len-k-1; i++) {pre=pre.next;}ListNode ans = pre.next;pre.next=null;return ans;}

寻找单链表的中点

思路：有两个指针，一个一次走2步，一个一次走1步。

/* @param {ListNode} head* @return {ListNode}*/
var middleNode = function(head) {let left = head;let right =head;while(right!=null&&right.next!=null){right = right.next.next;left = left.next;}return left
};

删除链表中的节点

给一个链表，删除node节点。给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head。正常删除节点的方式是 找到节点node ，找到节点的前一个节点 node -1，然后node -1 指向 node+1.

但是这道题，将该节点变成下一个节点的样子，然后去除下一节点（题目给的提示是保证给定的节点 node 不是链表中的最后一个节点。）

/* Definition for singly-linked list.* function ListNode(val) {*     this.val = val;*     this.next = null;* }*/
/* @param {ListNode} node* @return {void} Do not return anything, modify node in-place instead.*/
var deleteNode = function(node) {node.val = node.next.val;node.next = node.next.next;};

删除链表的中间节点

利用前两道题的寻找中间结点的时候 +删除结点

/* @param {ListNode} head* @return {ListNode}*/
//错误案例
var deleteMiddle = function(head) {let left = head;let right =head;while(right!=null&&right.next!=null){right = right.next.next;left = left.next;}// 删除某个结点，除了记录前一个结点，还有一种方式就是改头换面，但是这种方法只适用于删除的结点不是最后一个结点left.val = left.next.val;left.next = left.next.next;return head
};

// 删除某个结点：一般的方法要记录前一个结点
var deleteMiddle = function(head) {let left = head;let right =head;let pre = new ListNode(-1);pre.next = head;while(right!=null&&right.next!=null){right = right.next.next;left = left.next;pre = pre.next;}pre.next = left.next;return head
};

判断单链表是否包含环

每当慢指针 slow 前进一步，快指针 fast 就前进两步。

如果 fast 最终遇到空指针，说明链表中没有环；如果 fast 最终和 slow 相遇，那肯定是 fast 超过了 slow 一圈，说明链表中含有环。

/* @param {ListNode} head* @return {ListNode}*/
var hasCycle = function(head) {let left = head;let right =head;while(right!=null&&right.next!=null){right = right.next.next;left = left.next;if(right === left)return true;}return false
};

回文链表

单链表无法倒着遍历，把原始链表反转存入一条新的链表，然后比较这两条链表是否相同。

借助二叉树后序遍历的思路，不需要显式反转原始链表也可以倒序遍历链表

    /* 倒序打印单链表中的元素值*/function traverse(head) {if (head === null) {return;}traverse(head.next);// 后序遍历代码console.log(head.val);}~~~~~~js
/
* @param {ListNode} head
* @return {boolean}
*/var isPalindrome = function(head) {let left = head;const traverse=(head)=>{if(head===null) return true;let res = traverse(head.next);res = res && (head.val===left.val)left = left.next;return res;}return traverse(head);};

合并两个有序链表

思路一：新建，遍历两个链表，谁小就存谁。

var mergeTwoLists = function(l1, l2) {// function body goes here// dummy 虚拟头结点。let list = new ListNode();let head = list;while(l1!==null&&l2!==null){if(l1.val<l2.val){list.next = l1;l1=l1.next;}else{list.next = l2;l2= l2.next;}list = list.next;}// 如果没有比较完则将剩下的接起来。list.next = l1===null?l2:l1;return head.next;
};

合并 k 个有序链表

如何快速得到 k 个节点中的最小节点，接到结果链表上。

链表的分解

就是小于x的放在x前面。大于的放在x后面，不用排序。

思路就是遍历原有的链表，创建两个新的链表，小的链表在大的链表前面

【注意点】：要断开原链表之间的连接。

var partition = function(head, x) {let smallDummy = new ListNode(-1);let smallHead = smallDummy;let bigDummy = new ListNode(-1);let bigHead = bigDummy;while(head!=null){if(head.val<x){smallDummy.next = head;smallDummy = smallDummy.next;}else{bigDummy.next = head;bigDummy = bigDummy.next;}// 断开原链表中的每个节点的 next 指针let temp = head.next;head.next = nullhead = temp;}smallDummy.next = bigHead.next;return smallHead.next};

反转链表

指针+移动

虚拟结点

两个指针：pre ，head。将head 指向pre。pre从null开始。head 由第一个节点到达最后一个节点。由于head 指向了pre ，因此需要一个next 记录head 的下一个结点。

/* 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 reverseList = function(head) {let pre = null;while(head!=null){let next = head.next;head.next = pre;pre = head;head = next;}return pre;};

public ListNode reverseList(ListNode head){//一共三个指针，cur 指向前面pre，//还要有cur的next也要记录//移动的边界。nullListNode pre = null;while(head!= null){ListNode next = head.next;head.next = pre;pre = head;head = next;}return pre;}

反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表

/* @param {ListNode} head* @param {number} left* @param {number} right* @return {ListNode}*/
var reverseBetween = function(head, left, right) {let dummy = new ListNode(-1);dummy.next = head;let pre = dummy;let cur = head;let leftNode = head;for(let i =0;i<left-1;i++){cur = cur.next;pre = pre.next;leftNode = leftNode.next;}let next = cur.next;for(let i = left;i<right;i++){let temp = next.next;next.next = cur;cur = next;next = temp;}pre.next = cur;leftNode.next = next;return dummy.next};

K 个一组翻转链表

算到第k个执行一个翻转链表。

翻转链表的输入参数有头尾节点，因此结束循环的条件不再是head 不指向null。而是头节点！=尾节点

返回节点也是一个数组，存储着新节点。

虚拟结点，pre 不再是null，因为pre 有可能是结点。因此增加哨兵结点以统一处理。

public ListNode reverseKGroup(ListNode head, int k) {//思路：就是两个指针ListNode dummyNode = new ListNode();dummyNode.next = head;ListNode pre = dummyNode;while(head!=null){//定位首尾指针ListNode tail = pre;for (int i = 0; i < k; i++) {tail=tail.next;if(tail==null){return dummyNode.next;}}//除了首尾指针，还要有首指针的前一个，尾指针的后一个，才能将反装后的链表与原来的链表连接起来。ListNode next = tail.next;ListNode[] res=reverseList(head,tail);head = res[0];tail = res[1];pre.next=head;tail.next = next;head = next;pre = tail;}//结果就是返回哨兵结点的下一个结点。return dummyNode.next;}public ListNode[] reverseList(ListNode head,ListNode tail){ListNode pre = null;ListNode cur = head;//已知头尾反转链表，边界不再是nullwhile(pre!=tail){ListNode next = cur.next;cur.next = pre;pre = cur;cur=next;}//返回首尾return new ListNode[]{tail,head};}