链表反转
LC 206. Reverse Linked List 反转链表
https://leetcode.com/problems/reverse-linked-list/
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
prev := (*ListNode)(nil)
for head != nil {
next := head.Next
head.Next = prev
prev = head
head = next
}
return prev
}
递归解法
待复习
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
if head == nil {
return nil
}
if head.Next == nil {
return head
}
next := head.Next
newHead := reverseList(next)
next.Next = head
head.Next = nil
return newHead
}
反转链表前 N 个节点
func reverseN(head *ListNode, n int) *ListNode {
oldHead := head
prev := (*ListNode)(nil)
for i := 0; i < n; i++ {
next := head.Next
head.Next = prev
prev = head
head = next
}
newNext := prev
oldHead.Next = head
return newNext
}
LC 92. Reverse Linked List II 反转链表 II
https://leetcode.com/problems/reverse-linked-list-ii/
待复习
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseBetween(head *ListNode, left int, right int) *ListNode {
if left == 1 {
return reverseN(head, right-left+1)
}
h := head
prev := (*ListNode)(nil)
for i := 1; i < left; i++ {
prev = h
h = h.Next
}
newPartHead := reverseN(h, right-left+1)
prev.Next = newPartHead
return head
}
func reverseN(head *ListNode, n int) *ListNode {
oldHead := head
prev := (*ListNode)(nil)
for i := 0; i < n; i++ {
next := head.Next
head.Next = prev
prev = head
head = next
}
newNext := prev
oldHead.Next = head
return newNext
}
LC 25. K 个一组翻转链表
https://leetcode.com/problems/reverse-nodes-in-k-group/
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseKGroup(head *ListNode, k int) *ListNode {
l := getListLength(head)
if l < k {
return head
}
newHead := (*ListNode)(nil)
partHead := head
prevPartTail := (*ListNode)(nil)
for l >= k {
nextPartHead := reverseN(partHead, k)
if newHead == nil {
newHead = nextPartHead
}
if prevPartTail != nil {
prevPartTail.Next = nextPartHead
}
partHead = nextPartHead
for i := 0; i < k; i++ {
prevPartTail = partHead
partHead = partHead.Next
}
l -= k
}
return newHead
}
func getListLength(head *ListNode) int {
l := 0
for head != nil {
l++
head = head.Next
}
return l
}
func reverseN(head *ListNode, n int) *ListNode {
oldHead := head
prev := (*ListNode)(nil)
for i := 0; i < n; i++ {
next := head.Next
head.Next = prev
prev = head
head = next
}
newNext := prev
oldHead.Next = head
return newNext
}
双指针链表
LC 378. Kth Smallest Element in a Sorted Matrix 有序矩阵中第 K 小的元素
https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/
待复习
思路：合并 k 个有序链表
func kthSmallest(matrix [][]int, k int) int {
n := len(matrix)
pointers := make([]int, n)
result := 0
for i := 0; i < k; i++ {
minI := -1
minV := 10_000_000_000
for i, p := range pointers {
if p < n && matrix[i][p] < minV {
minI = i
minV = matrix[i][p]
}
}
result = minV
pointers[minI]++
}
return result
}
思路：合并 K 个有序链表 + 最小堆
func kthSmallest(matrix [][]int, k int) int {
n := len(matrix)
hv := make(CellHeap, 0, n)
h := &hv
for i := 0; i < n; i++ {
heap.Push(h, Cell{matrix[i][0], i, 0})
}
result := 0
for i := 0; i < k; i++ {
cell := heap.Pop(h).(Cell)
result = cell[0]
if cell[2] < n-1 {
r := cell[1]
c := cell[2]+1
heap.Push(h, Cell{matrix[r][c], r, c})
}
}
return result
}
type Cell [3]int
type CellHeap []Cell
func (h CellHeap) Len() int { return len(h) }
func (h CellHeap) Less(i, j int) bool { return h[i][0] < h[j][0] }
func (h CellHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *CellHeap) Push(x any) { *h = append(*h, x.(Cell)) }
func (h *CellHeap) Pop() any {
l := h.Len()
v := (*h)[l-1]
(*h) = (*h)[:l-1]
return v
}
思路：二分
func kthSmallest(matrix [][]int, k int) int {
n := len(matrix)
L, R := matrix[0][0], matrix[n-1][n-1]
for L <= R {
mid := L + (R - L) / 2
c := count(matrix, mid)
if c >= k {
R = mid - 1
} else {
L = mid + 1
}
}
return L
}
func count(matrix [][]int, x int) int {
n := len(matrix)
num := 0
i, j := n-1, 0
for i >= 0 && j < n {
if matrix[i][j] <= x {
num += i+1
j++
} else {
i--
}
}
return num
}