单链表排序方式
148 排序链表
链表排序
插入排序
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func insertionSortList(head *ListNode) *ListNode {
if head==nil{
return head
}
//定一个前置节点
dummy:=new(ListNode)
cur:=head
for cur!=nil{
//每次从前面的节点寻找大于cur的节点，插入此节点前面
pre:=dummy
for pre.Next!=nil&&pre.Next.Val<cur.Val{
pre = pre.Next
}
next:=cur.Next
//cur 放pre前面
cur.Next = pre.Next
pre.Next = cur
cur = next
}
return dummy.Next
}
归并递归
- 找中点,循环递归
func sortList(head *ListNode) *ListNode {
//快排链表 归并(递归迭代)
if head==nil{
return head
}
return sort(head)
}
//找中点
func sort(head *ListNode)*ListNode{
if head.Next==nil{ //一个直接返回
return head
}
slow,fast,pre:=head,head,head //快慢指针找中点,依据fast判断
for fast!=nil&&fast.Next!=nil{
pre = slow
slow = slow.Next
fast = fast.Next.Next
}
pre.Next = nil //断开链接
left:=sort(head) //左边递归
right:=sort(slow) //右边递归
return merge(left,right)
}
func merge(left,right *ListNode)*ListNode{
dummy:=new(ListNode)
pre:=dummy
for left!=nil&&right!=nil{
if left.Val<right.Val{
pre.Next = left
pre = pre.Next
left = left.Next
}else{
pre.Next = right
pre = pre.Next
right = right.Next
}
}
if left==nil{
pre.Next = right
}else{
pre.Next = left
}
return dummy.Next
}
归并迭代
快排链表
其他链表操作
138复制复杂链表
- 放置相同数值然后拆分
/**
* Definition for a Node.
* type Node struct {
* Val int
* Next *Node
* Random *Node
* }
*/
func copyRandomList(head *Node) *Node {
if head==nil{
return nil
}
//每个结点后放置相同数值的结点
for cur:=head;cur!=nil;cur = cur.Next.Next{
tmp:=new(Node)
tmp.Val = cur.Val
tmp.Next = cur.Next
cur.Next = tmp
}
//随机指针赋值
for cur:=head;cur!=nil;cur = cur.Next.Next{
tmp:=cur.Next
if cur.Random!=nil{ //不空则赋值下一个，否则默认nil
tmp.Random = cur.Random.Next
}
}
//拆解链表
res:=head.Next
for cur:=head;cur!=nil;cur = cur.Next{
tmp:=cur.Next
cur.Next = cur.Next.Next//连接原始链表
if tmp.Next!=nil{
tmp.Next = tmp.Next.Next
}
}
return res
}
143 重排链表
142 环形链表2
- 主要是公式的推导和for循环判断为fast!=nil
- 上一题用到环形链表思想
假设 slow 走距离 a+b ,fast走距离 a+n(b+c)
因为二倍,2(a+b) = a+n(b+c)+b,求a
a = n(b+c)-b = (n-1)(b+c)+c
所以从头走到环入口,距离为多倍的环+c,正好和slow在入口相遇
func detectCycle(head *ListNode) *ListNode {
slow,fast:=head,head
for fast!=nil{ //判断条件不是slow==fast
slow = slow.Next
if fast.Next==nil{
return nil //fast.Next为nil则不能继续进行
}
fast = fast.Next.Next
if slow==fast{
p:=head
for p!=slow{
p = p.Next
slow = slow.Next
}
return p
}
}
return nil
}