package _021_merge_two_sorted_lists

import . "gitee.com/dllearn/geektime-algorithm-learn/structures"

// 21. 合并两个有序链表
// https://leetcode-cn.com/problems/merge-two-sorted-lists/

/**
 * 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
	}

	var head *ListNode
	var c *ListNode
	if list1.Val <= list2.Val {
		head = list1
		list1 = list1.Next
	} else {
		head = list2
		list2 = list2.Next
	}
	c = head

	for list1 != nil && list2 != nil {
		if list1.Val <= list2.Val {
			head.Next = list1
			head = head.Next
			list1 = list1.Next
		} else {
			head.Next = list2
			head = head.Next
			list2 = list2.Next
		}
	}

	if list1 == nil {
		head.Next = list2
	}
	if list2 == nil {
		head.Next = list1
	}
	return c
}