链表¶
实现链表的排序¶
使用O(n logn)
的时间复杂度对链表进行排序
/* 链表排序
* 1、每一个节点是一个有序链表,当前节点与排好序的链表进行合并
* 2、合并两个有序链表,只需要两个当前指针进行比大小即可
* 3、O(n logn) 需要进行分治,合并是O(n), 分治才能0(log n)
* 4、两个快慢指针,快指针跳两下,慢指针跳一下,达到对半分治的效果
*/
func sortList(head *ListNode) *ListNode {
if head == nil || head.Next == nil { return head }
slow, fast := head, head
var prev *ListNode
for fast != nil && fast.Next != nil { // fast 比 slow 快一倍,即 slow 是半点
prev = slow
slow = slow.Next
fast = fast.Next.Next
}
prev.Next = nil
l1 := sortList(head)
l2 := sortList(slow)
return mergeTwoLists(l1,l2)
}
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
var tmp = &ListNode{}
var head = tmp
for l1!=nil && l2!=nil{
if(l1.Val < l2.Val){
tmp.Next = l1
l1 = l1.Next
tmp = tmp.Next
}else{
tmp.Next = l2
l2 = l2.Next
tmp = tmp.Next
}
}
if(l1 != nil){
tmp.Next = l1
}else if(l2 != nil){
tmp.Next = l2
}
return head.Next
}
实现高效的单向链表逆序输出¶
// 如何实现一个高效的单向链表逆序输出?
import "fmt"
type node struct {
data int
next *node
}
func reverse(head *node) {
if head == nil || head.next == nil {
return
}
var prev *node
var next *node
pcur := head
for pcur != nil {
if pcur.next == nil { //此时为最后一个节点
pcur.next = prev
break
}
next = pcur.next //取下一个节点
pcur.next = prev // 将当前节点挂在下一个节点 (pcur) 的后面
prev = pcur // 当前节点
pcur = next //将下一个节点指给 pcur
}
tmp := pcur
for tmp != nil {
fmt.Print(tmp.data, " ")
tmp = tmp.next
}
}
func main() {
var head *node = &node{data: 0, next: nil} //指针指向资源区
var varHead *node = head
fmt.Println("before:")
for i := 1; i < 6; i++ { // 构建链表
var tmp node = node{data: i, next: nil}
fmt.Print(tmp.data, " ")
varHead.next = &tmp
varHead = varHead.next
}
fmt.Println()
fmt.Println("after:")
reverse(head)
}