一个原则: 画图
两种题型: 指针的修改、链表的拼接
三个注意: 环、边界、递归
四个技巧:
虚拟头
若题目的头节点可能被移除/会变，则可以使用虚拟头节点，这样头节点就变成了中间节点，就不需要为头节点做特殊判断
通过在合适的时候断开链接，返回链表的中间节点
快慢指针
穿针引线
先穿再排后判空
Other: 若你想递归和迭代都写, 推荐前序遍历,因为前序遍历很容易改成迭代,准确的说前序遍历容易改成不需要栈的递归,而后续遍历则需要借助栈来完成
Summary: 如果是单链表,我们无法在O(1)的时间拿到前驱节点,这也是为什么我们遍历的时候老是维护一个前驱节点pre的原因。但是本质原因其实是链表的增删操作都依赖前驱节点。这是链表的基本操作,是链表的特性天生决定的
==上一行的赋值右边为下一行的赋值左边，赋值的时候从左边思考好理解==
插入
删除
Last updated
//pre待插入位置的前驱节点
next = pre.next
pre.next = targetInsertNode
targetInsertNode.next = next//pre待删除节点的前驱节点
pre.next = 待删除位置的前驱节点.next.nextvar addTwoNumbers = function (l1, l2) {
const dummyHead = new ListNode(-1)
let p1 = l1,
p2 = l2,
cur = dummyHead,
carry = 0
while (p1 || p2) {
const x = p1 !== null ? p1.val : 0
const y = p2 !== null ? p2.val : 0
const sum = x + y + carry
carry = sum >= 10 ? 1 : 0
cur.next = new ListNode(sum % 10)
// update cur
cur = cur.next
if (p1 !== null) p1 = p1.next
if (p2 !== null) p2 = p2.next
}
//最后的进位
if (carry === 1) cur.next = new ListNode(carry)
return dummyHead.next
}//basic version
var removeNthFromEnd = function (head, n) {
const dummyHead = new ListNode(-1, head)
const len = getLen(head)
let cur = dummyHead
//找到要删除节点的前驱结点
for (let i = 0; i < len - n; i++) cur = cur.next
cur.next = cur.next.next
return dummyHead.next
function getLen(head) {
let len = 0
while (head) {
len++
head = head.next
}
return len
}
}
//O(n) - O(1)
//fast slow pointer
var removeNthFromEnd = function (head, n) {
const dummyHead = new ListNode(-1, head)
let fast = dummyHead,
slow = dummyHead
//移完后fast和slow的距离是n
while (n >= 0) {
fast = fast.next
n--
}
//说明要删除的是头结点
if (!fast) return head.next
//同步走，slow走到要删除节点的前驱节点
while (fast) {
fast = fast.next
slow = slow.next
}
slow.next = slow.next.next
return dummyHead.next
}//iteration
var mergeTwoLists = function (list1, list2) {
const dummyHead = new ListNode(-1)
let cur = dummyHead
while (list1 && list2) {
if (list1.val < list2.val) {
cur.next = list1
list1 = list1.next
} else {
cur.next = list2
list2 = list2.next
}
//update cur
cur = cur.next
}
//合并后 l1 和 l2 至多只有一个还未被合并完,将链表末尾指向未合并完的链表
cur.next = list1 || list2
return dummyHead.next
}
//recursion
var mergeTwoLists = function (list1, list2) {
if (list1 == null) {
return list2
} else if (list2 == null) {
return list1
} else if (list1.val < list2.val) {
list1.next = mergeTwoLists(list1.next, list2)
//返回当前递归的头结点
return list1
} else {
list2.next = mergeTwoLists(list1, list2.next)
//同上
return list2
}
}//O(KN) - O(n)
var mergeKLists = function (lists) {
const len = lists.length
if (len === 0) return null
const mergeTwoLists = (l1, l2) => {
if (!l1) return l2
if (!l2) return l1
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2)
return l1
} else {
l2.next = mergeTwoLists(l1, l2.next)
return l2
}
}
let ret = lists[0]
for (let i = 1; i < len; i++) {
ret = mergeTwoLists(ret, lists[i])
}
return ret
}
//use array
var mergeKLists = function (lists) {
const len = lists.length
if (len === 0) return null
const arr = []
let cur
//add each node's val to arr
lists.forEach((list) => {
cur = list
while (cur) {
arr.push(cur.val)
cur = cur.next
}
})
const dummyHead = new ListNode(-1)
cur = dummyHead
let node
arr
.sort((a, b) => a - b)
.forEach((val) => {
node = new ListNode(val)
cur.next = node
cur = cur.next
})
return dummyHead.next
}
//O(NlogK) - O(n) 分治
var mergeKLists = function (lists) {
const len = lists.length
if (len === 0) return null
const mergeTwoLists = (l1, l2) => {
if (!l1) return l2
if (!l2) return l1
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2)
return l1
} else {
l2.next = mergeTwoLists(l1, l2.next)
return l2
}
}
const merge = (left, right) => {
if (left === right) return lists[left]
let mid = Math.floor((left + right) >> 1)
let l1 = merge(left, mid)
let l2 = merge(mid + 1, right)
return mergeTwoLists(l1, l2)
}
return merge(0, len - 1)
}//iteration, three pointer O(n) - O(1)
var swapPairs = function (head) {
const dummyHead = new ListNode(-1, head)
let cur = dummyHead
//够2个才换
while (cur.next && cur.next.next) {
const first = cur.next
const second = first.next
first.next = second.next
second.next = first
cur.next = second
cur = cur.next.next
}
return dummyHead.next
}
//recursion
var swapPairs = function (head) {
//当前没有节点或者只有一个节点,不需要交换
if (!head || !head.next) return head
// 需要交换的两个节点是 head 和 head.next
const first = head,
second = head.next
// first连接后面交换完成的子链表的头节点
first.next = swapPairs(second.next)
second.next = first
// 返回当前层交换完的子链表,second变成了头结点
return second
}var reverseKGroup = function (head, k) {
let a = head,
b = head
//遍历完b变成了下次翻转的头结点
for (let i = 0; i < k; i++) {
//不够数量直接返回
if (!b) return head
b = b.next
}
const newHead = reverse(a, b)
a.next = reverseKGroup(b, k)
return newHead
}
function reverse(a, b) {
let prev = null,
cur = a,
next
while (cur !== b) {
next = cur.next
cur.next = prev
prev = cur
cur = next
}
return prev
}var rotateRight = function (head, k) {
if (k === 0 || !head || !head.next) return head
let len = 1,
cur = head
//get length
//len initial is 1, so from cur.next begin loop， or cur.next = head throw null error
while (cur.next) {
cur = cur.next
len++
}
// 当k大于长度时, 又是一个轮回, 所以对长度取余
const num = k % len
// 不需要旋转
if (num === 0) return head
//form ring
cur.next = head
let index = 1,
newTail = head
//find new tail
while (index < len - num) {
newTail = newTail.next
index++
}
const newHead = newTail.next
//break ring
newTail.next = null
return newHead
}var deleteDuplicates = function (head) {
if (!head) return head
let dummyHead = new ListNode(-1, head)
let cur = dummyHead
while (cur.next && cur.next.next) {
if (cur.next.val === cur.next.next.val) {
const x = cur.next.val
while (cur.next && cur.next.val === x) {
cur.next = cur.next.next
}
} else {
cur = cur.next
}
}
return dummyHead.next
}var deleteDuplicates = function (head) {
let cur = head
while (cur && cur.next) {
if (cur.val === cur.next.val) {
cur.next = cur.next.next
} else {
cur = cur.next
}
}
return head
}
var deleteDuplicates = function (head) {
if (!head) return null
let fast = head,
slow = head
while (fast) {
if (fast.val !== slow.val) {
slow.next = fast
slow = slow.next
}
fast = fast.next
}
slow.next = null
return head
}//O(n) - O(1)
var partition = function (head, x) {
const dummyBefore = new ListNode(-1),
dummyAfter = new ListNode(-1)
let before = dummyBefore,
after = dummyAfter
//build before List and after List
while (head) {
if (head.val < x) {
before.next = head
before = before.next
} else {
after.next = head
after = after.next
}
head = head.next
}
after.next = null
before.next = dummyAfter.next
return dummyBefore.next
}//loop once
var reverseBetween = function (head, left, right) {
const dummyHead = new ListNode(-1)
dummyHead.next = head
let pre = dummyHead
for (let i = 0; i < left - 1; i++) {
pre = pre.next
}
let cur = pre.next
for (let i = 0; i < right - left; i++) {
const next = cur.next
//按顺序穿
cur.next = next.next
next.next = pre.next
pre.next = next
}
return dummyHead.next
}var getIntersectionNode = function (headA, headB) {
if (headA == null || headB == null) return null
let pa = headA,
pb = headB
while (pa != pb) {
pa = pa == null ? headB : pa.next
pb = pb == null ? headA : pb.next
}
return pa
}var sortedListToBST = function (head) {
const getMedian = (left, right) => {
let fast = (slow = left)
while (fast !== right && fast.next !== right) {
fast = fast.next.next
slow = slow.next
}
return slow
}
const buildTree = (left, right) => {
if (left === right) return null
const mid = getMedian(left, right)
const root = new TreeNode(mid.val)
//左闭右开
root.left = buildTree(left, mid)
root.right = buildTree(mid.next, right)
return root
}
//左闭右开
return buildTree(head, null)
}//O(n) - O(n)
var copyRandomList = function (head) {
const getCloneNode = (node) => {
if (node) {
if (visited.has(node)) {
return visited.get(node)
} else {
visited.set(node, new Node(node.val, null, null))
return visited.get(node)
}
}
return null
}
if (!head) return null
// Visited dictionary to hold old node reference as "key" and new node reference as the "value"
const visited = new Map()
let oldNode = head
let newNode = new Node(oldNode.val)
visited.set(oldNode, newNode)
while (oldNode) {
newNode.random = getCloneNode(oldNode.random)
newNode.next = getCloneNode(oldNode.next)
//move pointer forward,fill the attribute afterward
oldNode = oldNode.next
newNode = newNode.next
}
return visited.get(head)
}
//O(n) - O(1) 很难想出来
var copyRandomList = function (head) {
if (!head) return null
let ptr = head
//A->A'->B->B'->C->C'
while (ptr != null) {
const newNode = new Node(ptr.val)
newNode.next = ptr.next
ptr.next = newNode
ptr = newNode.next
}
ptr = head
//link the random pointer
while (ptr != null) {
ptr.next.random = ptr.random != null ? ptr.random.next : null
ptr = ptr.next.next
}
// A->B->C
let ptrOldList = head,
// A'->B'->C'
ptrNewList = head.next
const headOld = head.next
//切断链接
while (ptrOldList != null) {
ptrOldList.next = ptrOldList.next.next
ptrNewList.next = ptrNewList.next != null ? ptrNewList.next.next : null
ptrOldList = ptrOldList.next
ptrNewList = ptrNewList.next
}
return headOld
}//标记法 O(n) - O(1)
//或使用hash标记
var hasCycle = function (head) {
while (head) {
if (head.flag) {
return true
} else {
head.flag = true
head = head.next
}
}
return false
}
//fast and slow pointer O(n) - O(1)
var hasCycle = function (head) {
let fast = head,
slow = head
while (fast && fast.next) {
//先走再判断
fast = fast.next.next
slow = slow.next
if (fast === slow) return true
}
return false
}//标记法 O(n) - O(1)
//或使用hash标记
var detectCycle = function (head) {
let visited = new Set()
while (head) {
if (visited.has(head)) return head
visited.add(head)
head = head.next
}
return null
}
//fast and slow pointer O(n) - O(1)
//f=2s （快指针每次2步，路程刚好2倍）
//f = s + nb (相遇时，刚好多走了n圈）
//推出：s = nb
//从head结点走到入环点需要走 ： a + nb， 而slow已经走了nb，那么slow再走a步就是入环点了
//如何知道slow刚好走了a步? 从head开始，和slow指针一起走，相遇时刚好就是a步
var detectCycle = function (head) {
let slow = head,
fast = head
while (fast && fast.next) {
slow = slow.next
fast = fast.next.next
//第一次相遇,重定义fast,再走a步即再入口相遇
if (fast === slow) {
fast = head
while (fast !== slow) {
fast = fast.next
slow = slow.next
}
return fast
}
}
return null
}// O(n) - O(n)
var reorderList = function (head) {
if (!head) return
const arr = []
let cur = head
//add to array
while (cur) {
arr.push(cur)
cur = cur.next
}
//rebuild ListNode
let i = 0,
j = arr.length - 1
while (i < j) {
arr[i].next = arr[j]
i++
//当链表节点是偶数时
if (i === j) break
arr[j].next = arr[i]
j--
}
//cut the ring
arr[i].next = null
}var insertionSortList = function (head) {
if (!head || !head.next) return head
const dummyHead = new ListNode(-1, head)
//默认第一个已经排序，从第二个结点开始比
let lastSorted = head,
cur = head.next
while (cur) {
if (lastSorted.val <= cur.val) {
lastSorted = lastSorted.next
} else {
let prev = dummyHead
//从头开始找prev
while (prev.next.val <= cur.val) prev = prev.next
//插入到该插入的位置
lastSorted.next = cur.next
cur.next = prev.next
prev.next = cur
}
//update cur
cur = lastSorted.next
}
return dummyHead.next
}//O(n) - O(n)
var getIntersectionNode = function (headA, headB) {
let visited = new Set()
let cur = headA
while (cur) {
visited.add(cur)
cur = cur.next
}
cur = headB
while (cur) {
if (visited.has(cur)) return cur
cur = cur.next
}
return null
}
//O(n) - O(1)
var getIntersectionNode = function (headA, headB) {
if (!headA || !headB) return null
let pA = headA,
pB = headB
while (pA !== pB) {
pA = pA === null ? headB : pA.next
pB = pB === null ? headA : pB.next
}
return pA
}var removeElements = function (head, val) {
const dummyNode = new ListNode(-1, head)
let cur = dummyNode
while (cur.next) {
if (cur.next.val === val) {
cur.next = cur.next.next
continue
}
cur = cur.next
}
return dummyNode.next
}//iteration
var reverseList = function (head) {
let prev = null,
cur = head,
next
while (cur) {
next = cur.next
//change pointer ..3->2->1->null
cur.next = prev
//先移pre再移cur
prev = cur
cur = next
}
//返回反转后的头结点
return prev
}
//recursion
//翻转head.next且返回的是tail节点
var reverseList = function (head) {
if (!head || !head.next) return head
const tail = reverseList(head.next)
head.next.next = head
//cut the ring
head.next = null
//原本的tail变成了head，一直返回tail就是反转后的头结点
return tail
}//convert ListNode to Array O(n) - O(n)
var isPalindrome = function (head) {
const arr = []
while (head) {
arr.push(head.val)
head = head.next
}
let l = 0,
r = arr.length - 1
while (l < r) {
if (arr[l++] !== arr[r--]) return false
}
return true
}
//recursion
var isPalindrome = function (head) {
let first = head
const helper = (cur) => {
if (!cur) return true
if (!helper(cur.next)) return false
if (first.val !== cur.val) return false
first = first.next
return true
}
return helper(head)
}var oddEvenList = function (head) {
if (!head || !head.next) return head
const dummyHead1 = new ListNode(-1)
dummyHead1.next = head
const dummyHead2 = new ListNode(-1)
dummyHead2.next = head.next
let odd = dummyHead1.next
let even = dummyHead2.next
while (odd && odd.next && even && even.next) {
const oddNext = odd.next.next
const evenNext = even.next.next
odd.next = oddNext
even.next = evenNext
odd = oddNext
even = evenNext
}
odd.next = dummyHead2.next
return dummyHead1.next
}var middleNode = function (head) {
let n = 0,
cur = head
while (cur) {
n++
cur = cur.next
}
let k = 0
cur = head
while (k < Math.trunc(n / 2)) {
k++
cur = cur.next
}
return cur
}
//fast / slow
var middleNode = function (head) {
let fast = head,
slow = head
while (fast && fast.next) {
slow = slow.next
fast = fast.next.next
}
return slow
}