【从零开始的go刷题】合并两个有序链表

递归第一步就是找到边界，第二步是找到要保存的数据压入栈中，第三步考虑返回值和赋值的顺序

这题简单题递归居然卡了我半天，首先就是要一直递归到最后一个，然后才开始合并，边界就是list1或者list2为空。因为直接修改会丢失listm.next的信息，所以延后修改，让递归函数放回要修改的节点，自己将Next的信息压入递归函数（系统栈中）。list1.Next = mergeTwoLists(list1.Next, list2)
这里已经知道要找一个大的节点，将list1.Next压入栈中。
return list1 放回已经修改过的节点，前面已经递归有序了，当前修改的节点是第一个无序节点。
边界很好判断，单其中一个为nil了，上一个无序的节点只能指向不为nil的节点，很快能写出如下代码。

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	if list1 == nil {
		return list2
	}
	if list2 == nil {
		return list1
	}
	if list1.Val < list2.Val {
		mergeTwoLists(list1.Next, list2)
	} else {
		mergeTwoLists(list1, list2.Next)
	}
}

希望list.Next 信息不回消失，则延后赋值next，先记录递归返回的节点

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	if list1 == nil {
		return list2
	}
	if list2 == nil {
		return list1
	}
	if list1.Val < list2.Val {
		auto temp = mergeTwoLists(list1.Next, list2)
		list1.Next=list2
	} else {
		auto temp = mergeTwoLists(list1, list2.Next)
		list2.Next=list1
	}
}

但是list1.Next一定是指向list2吗？不一定，如何list1.Next比list2还小的话是指向list1.Next的。所以很容易写出代码

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	if list1 == nil {
		return list2
	}
	if list2 == nil {
		return list1
	}
	if list1.Val < list2.Val {
		list1.Next=mergeTwoLists(list1.Next, list2)
		return list1 //让上一层递归指向
	} else {
		list2.Next=mergeTwoLists(list1, list2.Next)
		return list2
	}
}

这样处了边界的两种，list1.Next 可能指向两个地方，一个是自己的Next，另外一个是list2。在下次递归返回出正确的节点。

提交

/*
 * @lc app=leetcode.cn id=21 lang=golang
 *
 * [21] 合并两个有序链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	if list1 == nil {
		return list2
	}
	if list2 == nil {
		return list1
	}
	if list1.Val < list2.Val {
		list1.Next = mergeTwoLists(list1.Next, list2) 
		return list1
	} else {
		list2.Next = mergeTwoLists(list1, list2.Next)
		return list2
	}
}

// @lc code=end