哨兵节点
哨兵节点是为了简化处理链表边界条件而引入的附加链表节点。哨兵节点通常位于链表的头部，它的值没有任何意义。在一个有哨兵节点的链表中，从第2个节点开始才真正保存有意义的信息。
- 用哨兵节点简化链表插入操作
- 用哨兵节点简化链表删除操作
双指针
- 删除倒数第k个节点
题目：如果给定一个链表，请问如何删除链表中的倒数第k个节点？假设链表中节点的总数为n，那么1≤k≤n。要求只能遍历链表一次。
/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/
var removeNthFromEnd = function(head, n) {
const dummy = new ListNode(0, head);
let front = head, back = dummy;
for(let i = 0;
i- 链表中环的入口节点
题目：如果一个链表中包含环，那么应该如何找出环的入口节点？从链表的头节点开始顺着next指针方向进入环的第1个节点为环的入口节点。例如，在如图4.3所示的链表中，环的入口节点是节点3。反转链表
- 反转链表
题目：定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点
var reverseList = function(head) {
const prev = null;
const cur = head;
while(cur != null) {
const next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return prev
}- 链表中的数组相加
题目：给定两个表示非负整数的单向链表，请问如何实现这两个整数的相加并且把它们的和仍然用单向链表表示？链表中的每个节点表示整数十进制的一位，并且头节点对应整数的最高位数而尾节点对应整数的个位数。【【算法】链表】分析：要考虑整数溢出的情况。
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
*this.val = (val===undefined ? 0 : val)
*this.next = (next===undefined ? null : next)
* }
*/var reverseList = function(head) {
let prev = null
let cur = head
while(cur !== null) {
const next = cur.next
cur.next = prev
prev = cur
cur = next
}
return prev
}/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function(l1, l2) {
let head1 = reverseList(l1)
let head2 = reverseList(l2)
let dummy = head = new ListNode(null)
let sub = 0
while(head1 !== null || head2 !== null) {
let a = head1 !== null ?head1.val :0
let b = head2 !== null ? head2.val :0
let val = a + b + sub
let node
if(val >= 10) {
val = val - 10
node = new ListNode(val)
sub =1
} else {
node = new ListNode(val)
sub = 0
}
head.next = node
head = head.next
head1 && (head1 = head1.next)
head2 && (head2 = head2.next)
}
if(sub==1) {
head.next = new ListNode(1)
head = head.next
}
return reverseList(dummy.next)
};
- 重排链表
问题：给定一个链表，链表中节点的顺序是L0→L1→L2→…→Ln-1→Ln，请问如何重排链表使节点的顺序变成L0→Ln→L1→Ln-1→L2→Ln-2→…？
- 切分链表
- 反转后半链表
- 链接链表
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
*this.val = (val===undefined ? 0 : val)
*this.next = (next===undefined ? null : next)
* }
*/
var reverseList = function(head) {
let prev = null
let cur = head
while(cur!==null) {
const next = cur.next
cur.next = prev
prev = cur
cur = next
}
return prev
}/**
* @param {ListNode} head
* @return {void} Do not return anything, modify head in-place instead.
*/
var reorderList = function(head) {
let dummy = new ListNode(0, head);
let fast = dummy, slow = dummy;
while(fast != null && fast.next != null) {
slow = slow.next
fast = fast.next.next
}const temp = slow.next;
slow.next = null;
link(head, reverseList(temp), dummy);
}var link = function(node1, node2, head) {
let prev = head;
while(node1 !== null && node2 !== null) {
const temp = node1.next;
prev.next = node1;
node1.next = node2
prev = node2node1 = temp
node2 = node2.next
}
if(node1 !== null) {
prev.next = node1
}
}- 回文链表
问题：如何判断一个链表是不是回文？要求解法的时间复杂度是O（n），并且不得使用超过O（1）的辅助空间。如果一个链表是回文，那么链表的节点序列从前往后看和从后往前看是相同的。例如，图4.13中的链表的节点序列从前往后看和从后往前看都是1、2、3、3、2、1，因此这是一个回文链表。
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
*this.val = (val===undefined ? 0 : val)
*this.next = (next===undefined ? null : next)
* }
*/
var reverseList = function(head) {
let prev = null
let cur = head
while(cur !== null) {
const next = cur.next
cur.next = prev
prev = cur
cur = next
}
return prev
}/**
* @param {ListNode} head
* @return {boolean}
*/
var isPalindrome = function(head) {
if(head == null || head.next == null) {
return true;
}
let slow = head;
let fast = head.next;
while(fast.next !== null && fast.next.next !== null) {
slow = slow.next
fast = fast.next.next
}
let secondHalf = slow.next;
if(fast.next != null) {
secondHalf = slow.next.next
}
slow.next = null;
return equals(secondHalf, reverseList(head))
}var equals = function(head1, head2) {
while(head1 != null && head2 !== null){
if(head1.val !== head2.val) return falsehead1 = head1.next
head2 = head2.next
}return head1 == null && head2 == null;
}双向链表和循环链表
- 展平多级双向链表
在一个多级双向链表中，节点除了有两个指针分别指向前后两个节点，还有一个指针指向它的子链表，并且子链表也是一个双向链表，它的节点也有指向子链表的指针。请将这样的多级双向链表展平成普通的双向链表，即所有节点都没有子链表。
var flatten = function(head) {}var flattenGetTail = function() {}- 排序的循环链表
问题：在一个循环链表中节点的值递增排序，请设计一个算法在该循环链表中插入节点，并保证插入节点之后的循环链表仍然是排序的。
