合并两个排序的链表

1. 题目描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

2. 思路

• 迭代：有点类似归并算法的合并步骤
• 递归

3. 实现

3.1. 迭代

• java

public class 合并两个排序的链表
{
    public ListNode Merge(ListNode list1, ListNode list2)
    {
        //检查参数
        if (list1 == null)
        {
            return list2;
        }
        if (list2 == null)
        {
            return list1;
        }

        //确定头节点
        ListNode newHead = list1.val < list2.val ? list1 : list2;
        ListNode current = newHead;
        //同时遍历两个链表
        while (list1 != null && list2 != null)
        {
            //较小的那个指向较大的那个
            ListNode nextNode = null;
            if (list1.val < list2.val)
            {
                nextNode = list1;
                list1 = list1.next;
            }
            else
            {
                nextNode = list2;
                list2 = list2.next;
            }
            current.next = nextNode;
            current = current.next;
        }

        //把剩下得链表连上
        if (list1 != null)
        {
            current.next = list1;
        }
        else if (list2 != null)
        {
            current.next = list2;
        }

        return newHead;
    }
}

• go

//迭代版本
//时间复杂度：O(m+n), m，n分别为两个单链表的长度
//空间复杂度：O(1)
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    dummyHead := &ListNode{}
    merged := dummyHead
    for list1 != nil && list2 != nil {
        if list1.Val < list2.Val {
            merged.Next = list1
            list1 = list1.Next
        }else {
            merged.Next = list2
            list2 = list2.Next
        }
        merged = merged.Next
    }
    if list1 != nil {
        merged.Next = list1
    }
    if list2 != nil {
        merged.Next = list2
    }
    return dummyHead.Next
}

3.2. 递归

//时间复杂度：O(m+n)
//空间复杂度：O(m+n),每一次递归，递归栈都会保存一个变量，最差情况会保存(m+n)个变量
func Merge2(pHead1 *ListNode, pHead2 *ListNode) *ListNode {
	if pHead1 == nil {
		return pHead2
	}
	if pHead2 == nil {
		return pHead1
	}

	if pHead1.Val < pHead2.Val {
		pHead1.Next = Merge2(pHead1.Next, pHead2)
		return pHead1
	} else {
		pHead2.Next = Merge2(pHead1, pHead2.Next)
		return pHead2
	}
}

4. 参考

• 合并两个排序的链表_牛客网
• 21. 合并两个有序链表 - 力扣（LeetCode）