package main
import "fmt"
func main() {
a := &ListNode{1, nil}
b := &ListNode{4, nil}
c := &ListNode{5, nil}
d := &ListNode{1, nil}
e := &ListNode{3, nil}
f := &ListNode{4, nil}
g := &ListNode{2, nil}
h := &ListNode{6, nil}
a.Next = b
b.Next = c
d.Next = e
e.Next = f
g.Next = h
lists := []*ListNode{a, d, g}
res := mergeKLists(lists)
for res != nil {
fmt.Println(res.Val)
res = res.Next
}
}
//合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
//
//示例:
//
//输入:
//[
// 1->4->5,
// 1->3->4,
// 2->6
//]
//输出: 1->1->2->3->4->4->5->6<Paste>
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
type ListNode struct {
Val int
Next *ListNode
}
type MinHeap struct {
Heap []*ListNode
Size int
Lens int //容量
}
func (this *MinHeap) Pop() *ListNode {
if this.Size == 0 {
return nil
}
res := this.Heap[0]
this.autoFixDown()
return res
}
func (this *MinHeap) autoFixDown() {
this.Heap[0] = this.Heap[this.Size-1]
this.Heap = this.Heap[:this.Size-1]
this.Size--
i := 0
j := 0
for i < this.Size {
child := &ListNode{0, nil}
hasChild := false
if i*2+2 < this.Size {
if this.Heap[i*2+2].Val < this.Heap[i*2+1].Val {
child = this.Heap[i*2+2]
j = i*2 + 2
hasChild = true
} else {
child = this.Heap[i*2+1]
j = i*2 + 1
hasChild = true
}
} else if i*2+1 < this.Size {
child = this.Heap[i*2+1]
j = i*2 + 1
hasChild = true
}
if hasChild && this.Heap[i].Val > child.Val {
this.Heap[i], this.Heap[j] = this.Heap[j], this.Heap[i]
i = j
} else {
break
}
}
}
func (this *MinHeap) Push(v *ListNode) bool {
if this.Size == this.Lens {
return false
}
if v == nil {
return false
}
this.Heap = append(this.Heap, v)
this.Size++
this.autoFixUp()
return true
}
func (this *MinHeap) autoFixUp() {
i := this.Size - 1
j := (i - 1) / 2
for i > 0 {
if this.Heap[i].Val < this.Heap[j].Val {
this.Heap[i], this.Heap[j] = this.Heap[j], this.Heap[i]
i = j
j = (i - 1) / 2
} else {
break
}
}
}
func mergeKLists(lists []*ListNode) *ListNode {
newHead := &ListNode{0, nil}
lens := len(lists)
mh := &MinHeap{[]*ListNode{}, 0, lens}
for _, v := range lists {
mh.Push(v)
}
item := mh.Pop()
newHead.Next = item
for item != nil {
if item.Next != nil {
mh.Push(item.Next)
}
item.Next = mh.Pop()
item = item.Next
}
return newHead.Next
}
//删除排序链表中的重复元素
//给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
//
//示例 1:
//
//输入: 1->1->2
//输出: 1->2
//示例 2:
//
//输入: 1->1->2->3->3
//输出: 1->2->3
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func deleteDuplicates(head *ListNode) *ListNode {
//if head == nil {
// return head
//}
//for item := head; item != nil; item = item.Next {
// for item.Next != nil && item.Val == item.Next.Val {
// item.Next = item.Next.Next
// }
//}
//return head
if head == nil {
return head
}
cur := head
for cur.Next != nil {
if cur.Val == cur.Next.Val {
cur.Next = cur.Next.Next
} else {
cur = cur.Next
}
}
return head
}
//反转链表
//反转一个单链表。
//
//示例:
//
//输入: 1->2->3->4->5->NULL
//输出: 5->4->3->2->1->NULL
//进阶:
//你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList1(head *ListNode) *ListNode {
if head == nil {
return head
}
item := head
next := item.Next
item.Next = nil
pre := item
item = next
for item != nil {
next := item.Next
item.Next = pre
pre = item
item = next
}
return pre
}
//递归算法
func reverseList2(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
newHead := reverseList(head.Next)
head.Next.Next = head
head.Next = nil
return newHead
}
//三个指针反转链表
func reverseList(head *ListNode) *ListNode {
first, ahead, flip := head, head, head
for ahead.Next != nil {
flip = ahead.Next
ahead.Next = flip.Next
flip.Next = first
first = flip
}
return first
}
//反转链表II
//反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
//
//说明:
//1 ≤ m ≤ n ≤ 链表长度。
//
//示例:
//
//输入: 1->2->3->4->5->NULL, m = 2, n = 4
//输出: 1->4->3->2->5->NULL
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseBetween(head *ListNode, m int, n int) *ListNode {
if head == nil {
return nil
}
newHead := &ListNode{0, head}
reverHead := newHead
for i := m - 1; i > 0; i-- {
reverHead = reverHead.Next
}
first, ahead, flip := reverHead.Next, reverHead.Next, reverHead.Next
time := n - m
for time > 0 {
flip = ahead.Next
ahead.Next = flip.Next
flip.Next = first
first = flip
time--
}
reverHead.Next = first
return newHead.Next
}
//删除排序链表中的重复元素II
//给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
//
//示例 1:
//
//输入: 1->2->3->3->4->4->5
//输出: 1->2->5
//示例 2:
//
//输入: 1->1->1->2->3
//输出: 2->3
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func deleteDuplicates2(head *ListNode) *ListNode {
newHead := &ListNode{}
newHead.Next = head
pre, cursor, sentry := newHead, newHead, newHead
for cursor.Next != nil {
sentry = cursor.Next
if sentry.Val != cursor.Val {
pre = cursor
cursor = sentry
} else {
for sentry.Val == cursor.Val {
if sentry.Next != nil {
sentry = sentry.Next
} else {
pre.Next = nil
return newHead.Next
}
}
pre.Next = sentry
cursor = sentry
}
}
return newHead.Next
}
func deleteDuplicates21(head *ListNode) *ListNode {
newHead := &ListNode{}
newHead.Next = head
pre := newHead
cur := head
for cur != nil {
for cur.Next != nil && cur.Next.Val == cur.Val {
cur = cur.Next
}
if pre.Next == cur {
pre = pre.Next
} else {
pre.Next = cur.Next
}
cur = cur.Next
}
return newHead.Next
}
//回文链表
//请判断一个链表是否为回文链表。
//
//示例 1:
//
//输入: 1->2
//输出: false
//示例 2:
//
//输入: 1->2->2->1
//输出: true
//进阶：
//你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
//获取中点，然后反转后半部分，然后比较
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func isPalindrome1(head *ListNode) bool {
return false
}
//判断列表是否有环
//给定一个链表，判断链表中是否有环。
//
//为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
//
//
//
//示例 1：
//
//输入：head = [3,2,0,-4], pos = 1
//输出：true
//解释：链表中有一个环，其尾部连接到第二个节点。
//
//
//示例 2：
//
//输入：head = [1,2], pos = 0
//输出：true
//解释：链表中有一个环，其尾部连接到第一个节点。
//
//
//示例 3：
//
//输入：head = [1], pos = -1
//输出：false
//解释：链表中没有环。
//
//
//
//
//进阶：
//
//你能用 O(1)（即，常量）内存解决此问题吗？
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func hasCycle(head *ListNode) bool {
walker, runner := head, head
for runner != nil && runner.Next != nil {
walker = walker.Next
runner = runner.Next.Next
if walker == runner {
return true
}
}
return false
}
//环形链表II
//给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
//
//为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
//
//说明：不允许修改给定的链表。
//
//
//
//示例 1：
//
//输入：head = [3,2,0,-4], pos = 1
//输出：tail connects to node index 1
//解释：链表中有一个环，其尾部连接到第二个节点。
//
//
//示例 2：
//
//输入：head = [1,2], pos = 0
//输出：tail connects to node index 0
//解释：链表中有一个环，其尾部连接到第一个节点。
//
//
//示例 3：
//
//输入：head = [1], pos = -1
//输出：no cycle
//解释：链表中没有环。
//
//
//
//
//进阶：
//你是否可以不用额外空间解决此题？
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func detectCycle(head *ListNode) *ListNode {
walker, runner := head, head
for runner != nil && runner.Next != nil {
walker = walker.Next
runner = runner.Next.Next
if runner == walker {
walker = head
for walker != runner {
walker = walker.Next
runner = runner.Next
}
return walker
}
}
return nil
}
//回文链表
//请判断一个链表是否为回文链表。
//
//示例 1:
//
//输入: 1->2
//输出: false
//示例 2:
//
//输入: 1->2->2->1
//输出: true
//进阶：
//你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func isPalindrome(head *ListNode) bool {
if head == nil || head.Next == nil {
return true
}
//获取中点
fast, slow := head, head
for fast != nil && fast.Next != nil {
fast = fast.Next.Next
slow = slow.Next
}
mid := slow
//反转链表
pre, cursor, sentry := mid, mid, mid
for cursor.Next != nil {
sentry = cursor.Next
cursor.Next = sentry.Next
sentry.Next = pre
pre = sentry
}
//判断链表是否相同
item := pre
for head != mid {
if head.Val != item.Val {
return false
}
head = head.Next
item = item.Next
}
return true
}
func echoList(head *ListNode) {
for head != nil {
fmt.Println(head.Val)
head = head.Next
}
}
//设计链表
//设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一 个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
//
//在链表类中实现这些功能：
//
//get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
//addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
//addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
//addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。
//deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
//
//
//示例：
//
//MyLinkedList linkedList = new MyLinkedList();
//linkedList.addAtHead(1);
//linkedList.addAtTail(3);
//linkedList.addAtIndex(1,2); //链表变为1-> 2-> 3
//linkedList.get(1); //返回2
//linkedList.deleteAtIndex(1); //现在链表是1-> 3
//linkedList.get(1); //返回3
//
//
//提示：
//
//所有值都在 [1, 1000] 之内。
//操作次数将在 [1, 1000] 之内。
//请不要使用内置的 LinkedList 库。
type MyLinkedList struct {
head *ListNode
tail *ListNode
size int
listMap []*ListNode
}
/** Initialize your data structure here. */
func Constructor() MyLinkedList {
return MyLinkedList{
nil, nil, 0, []*ListNode{},
}
}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
func (this *MyLinkedList) Get(index int) int {
if index < 0 || index > this.size-1 {
return -1
}
return this.listMap[index].Val
}
/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
func (this *MyLinkedList) AddAtHead(val int) {
node := &ListNode{val, this.head}
this.head = node
if this.size == 0 {
this.tail = this.head
}
this.listMap = append([]*ListNode{node}, this.listMap...)
this.size++
}
/** Append a node of value val to the last element of the linked list. */
func (this *MyLinkedList) AddAtTail(val int) {
node := &ListNode{val, nil}
this.listMap = append(this.listMap, node)
if this.tail == nil {
this.tail = node
this.head = node
} else {
this.tail.Next = node
this.tail = node
}
this.size++
}
/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
func (this *MyLinkedList) AddAtIndex(index int, val int) {
if index == 0 {
this.AddAtHead(val)
} else if index == this.size {
this.AddAtTail(val)
} else if index > this.size || index < 0 {
return
} else {
node := &ListNode{val, this.listMap[index]}
this.listMap[index-1].Next = node
restMap := append([]*ListNode{}, this.listMap[index:]...)
this.listMap = append(this.listMap[:index], node)
this.listMap = append(this.listMap, restMap...)
this.size++
}
}
/** Delete the index-th node in the linked list, if the index is valid. */
func (this *MyLinkedList) DeleteAtIndex(index int) {
if this.size == 0 {
return
} else if index < 0 || index > this.size-1 {
return
} else {
if this.size == 1 {
this.head = nil
this.tail = nil
this.listMap = []*ListNode{}
} else {
this.listMap[index-1].Next = this.listMap[index].Next
this.listMap = append(this.listMap[:index], this.listMap[index+1:]...)
}
this.size--
}
}
/**
* Your MyLinkedList object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Get(index);
* obj.AddAtHead(val);
* obj.AddAtTail(val);
* obj.AddAtIndex(index,val);
* obj.DeleteAtIndex(index);
*/
//重排链表
//给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
//将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
//
//你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
//
//示例 1:
//
//给定链表 1->2->3->4, 重新排列为 1->4->2->3.
//示例 2:
//
//给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reorderList(head *ListNode) {
if head == nil || head.Next == nil || head.Next.Next == nil {
return
}
//获取中点
fast, slow := head, head
for fast != nil && fast.Next != nil {
fast = fast.Next.Next
slow = slow.Next
}
restHead := slow.Next
slow.Next = nil
//反转第二个链表
left, cursor, sentry := restHead, restHead, restHead
for cursor.Next != nil {
sentry = cursor.Next
cursor.Next = sentry.Next
sentry.Next = left
left = sentry
}
for item1, item2 := head, left; item2 != nil; {
tmp1, tmp2 := item1, item2
item1, item2 = item1.Next, item2.Next
tmp2.Next = tmp1.Next
tmp1.Next = tmp2
}
}
//k个一组翻转链表
//给出一个链表，每 k 个节点一组进行翻转，并返回翻转后的链表。
//
//k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么将最后剩余节点保持原有顺序。
//
//示例 :
//
//给定这个链表：1->2->3->4->5
//
//当 k = 2 时，应当返回: 2->1->4->3->5
//
//当 k = 3 时，应当返回: 3->2->1->4->5
//
//说明 :
//
//你的算法只能使用常数的额外空间。
//你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseKGroup(head *ListNode, k int) *ListNode {
if head == nil || k == 0 || k == 1 {
return head
}
//获取长度
lens := 0
for item := head; item != nil; item = item.Next {
lens++
}
//获取重复的次数
time := lens / k
step := k
newHead := &ListNode{Next: head}
preCursor, left, cursor, sentry := newHead, head, head, head
for time > 0 {
for step > 1 {
sentry = cursor.Next
cursor.Next = sentry.Next
sentry.Next = left
left = sentry
step--
}
preCursor.Next = left
if cursor.Next == nil {
break
}
preCursor, left, cursor, sentry = cursor, cursor.Next, cursor.Next, cursor.Next
time--
step = k
}
return newHead.Next
}
//链表排序
//在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
//
//示例 1:
//
//输入: 4->2->1->3
//输出: 1->2->3->4
//示例 2:
//
//输入: -1->5->3->4->0
//输出: -1->0->3->4->5
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func sortList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
preSlow, fast, slow := head, head, head
for fast != nil && fast.Next != nil {
preSlow = slow
fast = fast.Next.Next
slow = slow.Next
}
fast = preSlow
fast.Next = nil
return mergeList(sortList(head), sortList(slow))
}
func mergeList(a, b *ListNode) *ListNode {
head, tail := b, b
item1, item2 := a, b.Next
if a.Val < b.Val {
head, tail = a, a
item1, item2 = a.Next, b
}
for item1 != nil || item2 != nil {
if item1 != nil && item2 != nil {
if item1.Val < item2.Val {
tail.Next = item1
tail = item1
item1 = item1.Next
} else {
tail.Next = item2
tail = item2
item2 = item2.Next
}
} else if item2 == nil {
tail.Next = item1
tail = item1
item1 = item1.Next
} else if item1 == nil {
tail.Next = item2
tail = item2
item2 = item2.Next
}
}
return head
}
//链表中点
//给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
//
//如果有两个中间结点，则返回第二个中间结点。
//
//
//
//示例 1：
//
//输入：[1,2,3,4,5]
//输出：此列表中的结点 3 (序列化形式：[3,4,5])
//返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
//注意，我们返回了一个 ListNode 类型的对象 ans，这样：
//ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
//示例 2：
//
//输入：[1,2,3,4,5,6]
//输出：此列表中的结点 4 (序列化形式：[4,5,6])
//由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
//
//
//提示：
//
//给定链表的结点数介于 1 和 100 之间。
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func middleNode(head *ListNode) *ListNode {
fast, slow := head, head
for fast != nil && fast.Next != nil {
fast = fast.Next.Next
slow = slow.Next
}
return slow
}
//奇偶链表
//给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
//
//请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
//
//示例 1:
//
//输入: 1->2->3->4->5->NULL
//输出: 1->3->5->2->4->NULL
//示例 2:
//
//输入: 2->1->3->5->6->4->7->NULL
//输出: 2->3->6->7->1->5->4->NULL
//说明:
//
//应当保持奇数节点和偶数节点的相对顺序。
//链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func oddEvenList(head *ListNode) *ListNode {
}