LC 21. Merge Two Sorted Lists 合并两个有序链表
https://leetcode.com/problems/merge-two-sorted-lists/
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
dummy := &ListNode{}
h := dummy
h1, h2 := list1, list2
for h1 != nil && h2 != nil {
if h1.Val < h2.Val {
h.Next = h1
h1 = h1.Next
h = h.Next
} else {
h.Next = h2
h2 = h2.Next
h = h.Next
}
}
for h1 != nil {
h.Next = h1
h1 = h1.Next
h = h.Next
}
for h2 != nil {
h.Next = h2
h2 = h2.Next
h = h.Next
}
return dummy.Next
}
LC 86. Partition List 分隔链表
https://leetcode.com/problems/partition-list/
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func partition(head *ListNode, x int) *ListNode {
dummy1, dummy2 := &ListNode{}, &ListNode{}
h1, h2 := dummy1, dummy2
for head != nil {
if head.Val < x {
h1.Next = head
h1 = h1.Next
head = head.Next
} else {
h2.Next = head
h2 = h2.Next
head = head.Next
}
}
h1.Next = dummy2.Next
h2.Next = nil
return dummy1.Next
}
LC 23. Merge k Sorted Lists 合并 K 个有序链表
https://leetcode.com/problems/merge-k-sorted-lists/
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeKLists(lists []*ListNode) *ListNode {
dummy := &ListNode{}
h := dummy
for {
minValue := 10_0000
minValuePI := -1
for i, h := range lists {
if h != nil {
if h.Val < minValue {
minValue = h.Val
minValuePI = i
}
}
}
if minValuePI == -1 {
break
} else {
h.Next = lists[minValuePI]
h = h.Next
lists[minValuePI] = lists[minValuePI].Next
}
}
h.Next = nil
return dummy.Next
}
利用最小堆优化时间复杂度
待复习
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeKLists(lists []*ListNode) *ListNode {
dummy := &ListNode{}
p := dummy
h := NodeHeap{}
for _, l := range lists {
p := l
for p != nil {
heap.Push(&h, p)
p = p.Next
}
}
for len(h) > 0 {
node := heap.Pop(&h).(*ListNode)
p.Next = node
p = p.Next
}
p.Next = nil
return dummy.Next
}
type NodeHeap []*ListNode
func (h NodeHeap) Len() int {
return len(h)
}
func (h NodeHeap) Less(i, j int) bool {
return h[i].Val < h[j].Val
}
func (h NodeHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *NodeHeap) Push(x any) {
*h = append(*h, x.(*ListNode))
}
func (h *NodeHeap) Pop() any {
node := (*h)[len(*h)-1]
*h = (*h)[:len(*h)-1]
return node
}
LC 19. Remove Nth Node From End of List 删除链表的倒数第 N 个节点
https://leetcode.com/problems/remove-nth-node-from-end-of-list/
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func removeNthFromEnd(head *ListNode, n int) *ListNode {
dummy := &ListNode{Next: head}
p := getNthFromEnd(dummy, n+1)
p.Next = p.Next.Next
return dummy.Next
}
func getNthFromEnd(head *ListNode, c int) *ListNode {
slow, fast := head, head
for i := 0; i < c; i++ {
fast = fast.Next
}
for fast != nil {
slow = slow.Next
fast = fast.Next
}
return slow
}
LC 876. Middle of the Linked List 链表的中间节点
https://leetcode.com/problems/middle-of-the-linked-list/description/
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func middleNode(head *ListNode) *ListNode {
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
return slow
}
LC 142. 环形链表 II
待复习
https://leetcode.com/problems/linked-list-cycle-ii/description/
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func detectCycle(head *ListNode) *ListNode {
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast {
break
}
}
if fast == nil || fast.Next == nil {
return nil // no cycle
}
slow = head
for slow != fast {
slow = slow.Next
fast = fast.Next
}
return fast
}