21.E 合并两个有序链表

Problem: 21. 合并两个有序链表

思路

思路1：

• 先设置一个哨兵指针，设置pre为哨兵指针。

  • 当list1和list2都不为空时，让pre指向值较小的链表的节点，然后该链表往后走一步。

  • 如果其中一个为空，则把pre指向另一个。

思路2:

递归。

• 如果任意一个链表为空，则返回另一个链表。

• 否则：

  • 如果list1的值较小，则让list1的节点指向递归合并mergeTwoLists(list1.Next, list2)的结果

  • 如果list2的值较小，则让list2的节点指向递归合并mergeTwoLists(list1, list2.Next)的结果

Code

代码1：

func mergeTwoListsV1(list1 *ListNode, list2 *ListNode) *ListNode {
	var newHead = &ListNode{Val: -1}
	var pre = newHead
	for list1 != nil && list2 != nil {
		if list1.Val <= list2.Val {
			pre.Next = list1
			list1 = list1.Next
		} else {
			pre.Next = list2
			list2 = list2.Next
		}

		pre = pre.Next
	}

	if list1 == nil {
		pre.Next = list2
	} else {
		pre.Next = list1
	}

	return newHead.Next
}

代码2：

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