Week 50 @ 2024 算法周记【链表反转 + 双指针链表】
- Bryan
Owned by Bryan
链表反转
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/
待复习
LC 25. K 个一组翻转链表
https://leetcode.com/problems/reverse-nodes-in-k-group/
双指针链表
LC 378. Kth Smallest Element in a Sorted Matrix 有序矩阵中第 K 小的元素
https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/
待复习
思路：合并 k 个有序链表
思路：合并 K 个有序链表 + 最小堆
思路：二分