th353453.jpg
141. 环形链表
原题链接：https://leetcode-cn.com/problems/linked-list-cycle/
假设有 a 和 b 两个指针，一慢一快，如果链表是有环状的，那么走的快的那个指针迟早会跟慢指针重合
var hasCycle = function(head) {
var fast = slow = head
while (slow && fast && fast.next) {
slow = slow.next
fast = fast.next.next
if(slow === fast) {
return true
}
}
return false
};
21. 合并两个有序链表
原题链接：https://leetcode-cn.com/problems/merge-two-sorted-lists/
每次比较两个
l1.val与l2.val的大小，取小的值，同时更新小的值指向下一个节点主要注意的就是循环终止的条件：当两者其中有一个为空时，即指向
null最后需要判断两个链表哪个非空，在将非空的链表与
tmp哨兵节点连接。
var mergeTwoLists = function(l1, l2) {
let newNode = new ListNode('start'), tmp = newNode
while(l1 && l2) {
if (l1.val >= l2.val) {
tmp.next = l2
l2 = l2.next
} else {
tmp.next = l1
l1 = l1.next
}
tmp = tmp.next
}
tmp.next = l1 == null ? l2 : l1
return newNode.next
};
203. 移除链表元素
原题链接：https://leetcode-cn.com/problems/remove-linked-list-elements/
var removeElements = function(head, val) {
if (head === null) {
return head
}
head.next = removeElements(head.next, val)
return head.val === val ? head.next : head
}
234. 回文链表
原题链接：https://leetcode-cn.com/problems/palindrome-linked-list/
寻找中间节点，之后将右边的节点进行翻转，比对两边的节点是否相同。
let isPalindrome = function(head) {
let right = reverse(findCenter(head))
let left = head
while(right !== null) {
if (left.val !== right.val) {
return false
}
left = left.next
right = right.next
}
return true
}
function reverse(head) {
if (!head) return null
let cur = head
let pre = null
while(cur !== null) {
let temp = cur.next
cur.next = pre
pre = cur
cur = temp
}
return pre
}
function findCenter(head) {
let faster = head, slower = head
while(slower && faster.next && faster.next.next) {
slower = slower.next
faster = faster.next.next
}
if (faster !== null) {
slower = slower.next
}
return slower
}
206. 反转链表
原题链接：https://leetcode-cn.com/problems/reverse-linked-list/
var reverseList = function(head) {
if (!head) return null
let pre = null
let cur = head
while(cur !== null) {
var temp = cur.next
cur.next = pre
// 改变两个指针的指向
pre = cur
// 走向下一个节点位置（位置信息存储在 temp 中）
cur = temp
}
return pre
}
148. 排序链表
原题链接：https://leetcode-cn.com/problems/sort-list/
let sortList = function (head) {
return mergeSortRec(head)
}
// 归并排序
// 若分裂后的两个链表长度不为 1，则继续分裂
// 直到分裂后的链表长度都为 1，
// 然后合并小链表
let mergeSortRec = function (head) {
if (!head || !head.next) {
return head
}
// 获取中间节点
let middle = middleNode(head)
// 分裂成两个链表
let temp = middle.next
middle.next = null
let left = head, right = temp
// 继续分裂（递归分裂）
left = mergeSortRec(left)
right = mergeSortRec(right)
// 合并两个有序链表
return mergeTwoLists(left, right)
}
// 获取中间节点
// - 如果链表长度为奇数，则返回中间节点
// - 如果链表长度为偶数，则有两个中间节点，这里返回第一个
let middleNode = function (head) {
let fast = head, slow = head
while (fast && fast.next && fast.next.next) {
slow = slow.next
fast = fast.next.next
}
return slow
}
// 合并两个有序链表
let mergeTwoLists = function (l1, l2) {
let preHead = new ListNode(-1);
let cur = preHead;
while (l1 && l2) {
if (l1.val < l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = l1 || l2;
return preHead.next;
}
160. 相交链表
原题链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
一直不断的循环，如果二者相交，那么指针一定会相遇
function getIntersectionNode(headA, headB) {
let pointA = headA;
let pointB = headB;
while (pointA || pointB) {
if (pointA === pointB) {
return pointA;
}
pointA = pointA === null ? headA : pointA.next;
pointB = pointB === null ? headB : pointB.next;
}
return null;
}
19. 删除链表的倒数第N个节点
原题链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
const removeNthFromEnd = function(head, n) {
let prev = new ListNode(0)
prev.next = head
let fast = prev
let slow = prev
// fast 指针指向 n 的位置
while(n--) {
fast = fast.next
}
// 等 fast 走到最后一个位置的时候，slow 就在删除节点的前一个节点
while(fast && fast.next) {
fast = fast.next
slow = slow.next
}
// 删除节点
slow.next = slow.next.next
return prev.next
}
83. 删除排序链表中的重复元素
原题链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/
var deleteDuplicates = function (head) {
if (head === null || head.next === null) {
return head
}
head.next = deleteDuplicates(head.next)
if (head.val === head.next.val) {
head = head.next
}
return head
};
25. K 个一组翻转链表
原题链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
var reverseKGroup = (head, k) => {
let reverseList = (start, end) => {
let [pre, cur] = [start, start.next],
front = cur;
// 终止条件就是cur当前节点不能等于end节点
// 翻转的套路
while (cur !== end) {
let next = cur.next
cur.next = pre
pre = cur
cur = next
}
front.next = end // 新翻转链表需要连接,也就是front指向原来区间后一个节点
start.next = pre // 新翻转的开头需要连接start.next
return front // 返回翻转后需要连接链表,也就是front指向
}
let newNode = new ListNode('start')
newNode.next = head;
let [start, end] = [newNode, newNode.next],
count = 0;
while (end !== null) {
count++
if (count % k === 0) {
// k个节点翻转后,又重新开始,返回值就是end节点前面一个
start = reverseList(start, end.next)
end = start.next
} else {
//不是一个分组就指向下一个节点
end = end.next
}
}
return newNode.next
};
