Go 语言实现链表的归并排序

• 输入: 数字序列的个数，一串数字序列
• 输出: 首先将这串序列转化为链表的形式，然后进行归并排序

归并排序的思路

归并排序首先采用二分的方式，递归的将序列切分成多个小块，并将这些小块逐级的生成更大的有序的块，
最后完成全部的排序。

可以用一个简图来表示：

代码实现

采用 golang 实现的代码如下，其中合并两个链表的方法参考了剑指 offer 中的面试题 25

package main

import (
	"fmt"
)

type Node struct {
	Val int
	Next *Node
}

func (node Node) print() {
	ptr := &node
	for ptr != nil {
		fmt.Println(ptr.Val)
		ptr = ptr.Next
	}
}

func (node Node) length() int {
	ptr := &node
	cnt := 0
	for ptr != nil {
		ptr = ptr.Next
		cnt += 1
	}
	return cnt
}

func (node Node) index(idx int) *Node {
	ptr := &node
	for i := 0; i < idx; i++ {
		ptr = ptr.Next
	}
	return ptr
}

func split(node *Node, leftLength int) (*Node, *Node) {
	leftNode := node
	rightNode := node.index(leftLength)
	node.index(leftLength-1).Next = nil
	return leftNode, rightNode
}

func merge(left *Node, right *Node) *Node {
	if left == nil {
		return right
	} else if right == nil {
		return left
	}

	var mergeHead *Node

	if left.Val < right.Val {
		mergeHead = left
		mergeHead.Next = merge(left.Next, right)
	} else {
		mergeHead = right
		mergeHead.Next = merge(left, right.Next)
	}
	return mergeHead
}

func mergeSort(node *Node, length int) *Node {
	if node == nil {
		return nil
	}
	if length > 1 {
		leftLength := length / 2
		leftPtr, rightPtr := split(node, length / 2)
		leftNode := mergeSort(leftPtr, leftLength)
		rightNode := mergeSort(rightPtr, length-leftLength)
		mergeNodeHead := merge(leftNode, rightNode)
		return mergeNodeHead
	} else {
		node.Next = nil
		return node
	}
}

func genList(valArr []int) *Node{
	if len(valArr) == 0 {
		return nil
	}

	head := &Node {valArr[0], nil}
	nodePtr := head
	for i := 1; i < len(valArr); i++ {
		nodePtr.Next = &Node {valArr[i], nil}
		nodePtr = nodePtr.Next
	}
	return head
}

func main() {
	var cnt int
	fmt.Scanf("%d", &cnt)
	var valArr []int
	for i :=0; i < cnt; i++ {
		var tmp int
		fmt.Scanf("%d", &tmp)
		valArr = append(valArr, tmp)
	}
	node := genList(valArr)
	node = mergeSort(node, node.length())
	node.print()
}