本文共 2664 字，大约阅读时间需要 8 分钟。

package mainimport "fmt"type ListNode struct {	Val int	Next *ListNode}//头结点，不存储元素，主要用于头插法type LinkList struct {	HeadNode *ListNode}//头插法,原来的头结点始终不变，只是将原来的头结点的HeadNode指向新申请结点//新申请的结点又指向了原来头结点指向的结点func (self *LinkList) AddHead(value int){	//申请一个节点	newNode := &ListNode{Val:value}	newNode.Next = self.HeadNode	self.HeadNode = newNode}//尾插法，需要从头部开始遍历到结尾,也就是直到nilfunc (self *LinkList) Append(value int){	//申请待插入结点	newNode := &ListNode{Val:value}	//为遍历申请临时结点	tmpNode := self.HeadNode	if tmpNode == nil{		tmpNode = newNode	} else {		for tmpNode.Next != nil{			tmpNode =tmpNode.Next		}		//退出循环说明到了最后一个结点		tmpNode.Next = newNode	}}//链表长度func (self *LinkList) Length() int {	length := 0	tmpNode := self.HeadNode	for tmpNode != nil {		length += 1		tmpNode = tmpNode.Next	}	return length}//指定位置插入func (self *LinkList) Insert(pos, value int){	//申请待插入结点	newNode := &ListNode{Val:value}	//为遍历申请临时结点	tmpNode := self.HeadNode	if pos < 0 {		//负数默认头插法		self.AddHead(value)	}else if pos>self.Length() {		self.Append(value)	}else{		index := 0		for index < (pos - 1) {			tmpNode = tmpNode.Next			index += 1		}		//此时的index为目标位置，		//此时新节点接上此刻tmpNode之前连接的结点，tmpNode后接上新节点，即可		newNode.Next = tmpNode.Next		tmpNode.Next = newNode	}}//循环输出链表func (self *LinkList) PrintLinkList(){	tmpNode := self.HeadNode	for tmpNode != nil {		fmt.Print(tmpNode.Val)		tmpNode = tmpNode.Next	}}//链表排序func SortList(head *ListNode) *ListNode {	if head == nil || head.Next == nil {		return head	}	left, right := split(head)	return merge(SortList(left), SortList(right))}// 从中间位置，切分 listfunc split(head *ListNode) (left, right *ListNode) {	// head.Next != nil	// 因为， sortList 已经帮忙检查过了	// fast 的变化速度是 slow 的两倍	// 当 fast 到达末尾的时候，slow 正好在 list 的中间	slow, fast := head, head	var slowPre *ListNode	for fast != nil && fast.Next != nil {		slowPre, slow = slow, slow.Next		fast = fast.Next.Next	}	// 斩断 list	slowPre.Next = nil	// 使用 slowPre 是为了确保当 list 的长度为 2 时，会均分为两个长度为 1 的子 list	left, right = head, slow	return}// 把已经排序好了的两个 list left 和 right// 进行合并func merge(left, right *ListNode) *ListNode {	// left != nil , right != nil	// 因为， sortList 已经帮忙检查过了	cur := &ListNode{}	headPre := cur	for left != nil && right != nil {		// cur 总是接上较小的 node		if left.Val < right.Val {			cur.Next, left = left, left.Next		} else {			cur.Next, right = right, right.Next		}		cur = cur.Next	}	// 处理 left 或 right 中，剩下的节点	if left == nil {		cur.Next = right	} else {		cur.Next = left	}	return headPre.Next}func main()  {	lst := &LinkList{}	lst.AddHead(1)	lst.AddHead(2)	lst.Append(3)	lst.Append(4)	lst.Insert(1,9)	fmt.Print("排序前：")	lst.PrintLinkList()	fmt.Println()	lst.HeadNode = SortList(lst.HeadNode)	fmt.Print("排序后：")	lst.PrintLinkList()}

结果：

转载地址：http://mzwsi.baihongyu.com/