通过递归合并两个有序链表

1 -> 4 -> 5

1 -> 3 -> 4

合并之后： 1 -> 1 -> 3 -> 4 ->4 -> 5

func main() {

	testCombine()

}

type Node struct{
	val int
	next *Node
}

//合并两个有序链表
func combineSortedLink(left, right *Node) *Node {
	if left == nil {
		return right
	}
	if right == nil {
		return left
	}

	if left.val < right.val {
		left.next = combineSortedLink(left.next, right)
		return left
	} else {
		right.next = combineSortedLink(left, right.next)
		return right
	}
}


func testCombine()  {
	n1 := &Node{
		val: 1,
		next: &Node{
			val: 4,
			next: &Node{
				val: 5,
			},
		},
	}

	n2 := &Node{
		val: 1,
		next: &Node{
			val: 3,
			next: &Node{
				val: 4,
			},
		},
	}
	n := combineSortedLink(n1, n2)
	n.printNode()
}


func (n *Node) printNode() {
	for n != nil {
		fmt.Printf("%d \t ", n.val)
		n = n.next
	}
	fmt.Println()
}

输出结果： 1      1      3      4      4      5