链表题目练习
序号对应Leedcode题序，解题思路在上篇已提到，这里为具体代码实现，使用JavaScript
1. 单链表反转 206
function reverseList(link) {
if (!link || !link.next) return link;
let prev = null; // 反转链表头结点
let cur = link; // 当前待反转结点
let next = null; // 待反转下一个节点（存储）
while(cur) {
next = cur.next; // 存储
cur.next = prev; // 指针反转
prev = cur;
cur = next;
}
// 输出反转链表
return prev;
}
2. 链表中环的检测 141
function hasCycle(head) {
while(head) {
if (head.val === 'tip') {
return true;
}else{
head.val = 'tip';
head = head.next;
}
}
return false;
}
3. 两个有序的链表合并 21
function mergeTwoLists (l1,l2){
if (!l1) return l2;
if (!l2) return l1;
let result = null;
if (l1.val > l2.val) {
result = l2;
result.next = mergeTwoLists(l1,l2.next);
}else{
result = l1;
result.next = mergeTwoLists(l1.next,l2);
}
return result;
}
4. 删除链表倒数第 n 个结点 19
function removeNthFromEnd(head,n){
// 定义虚拟节点
let list = new ListNode(-1, head);
let slow = list;
let quick = head;
while(n--){
quick = quick.next;
}
// 快指针走到底了 删除的是头节点
if (!quick) {
return list.next.next;
}
while(quick) {
slow = slow.next;
quick = quick.next;
}
slow.next = slow.next.next;
return list.next;
}
5. 求链表的中间结点 876
function middleNode(head) {
let slow = head;
let quick = head;
while(quick && quick.next) {
slow = slow.next;
quick = quick.next.next;
}
return slow;
}
