006.合并两个有序链表

• 21.合并两个有序链表

进阶：你是否可以使用 O(1) 空间解决此题？

合并两个有序链表 - 原地合并

/**
 * 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, list2 = list2, list1
	}
	head := list1
	prev := head
	for list1 != nil && list2 != nil {
		if list1.Val <= list2.Val {
			prev = list1
			list1 = list1.Next
		} else {
			prev.Next = list2
			prev = list2
			list2 = list2.Next
			prev.Next = list1
		}
	}
 
	if list1 != nil {
		prev.Next = list1
	}
	if list2 != nil {
		prev.Next = list2
	}
 
	return head
}