题目链接

牛客在线oj题——合并两个排序的链表

题目描述

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。

数据范围： 0≤n≤1000，−1000≤节点值≤1000

要求：空间复杂度 O(1)，时间复杂度 O(n)

如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：
在这里插入图片描述
或输入{-1,2,4},{1,3,4}时，合并后的链表为{-1,1,2,3,4,4}，所以对应的输出为{-1,1,2,3,4,4}，转换过程如下图所示：

题目示例

示例1

输入：
{1,3,5},{2,4,6}

返回值：
{1,2,3,4,5,6}

示例2

输入：
{},{}

返回值：
{}

示例3

输入：
{-1,2,4},{1,3,4}

返回值：
{-1,1,2,3,4,4}

解题思路一

构造一个新的head和end指针，第一次比较list1的val和list2的val，如果list1的val小于list2的值，head和end等于list1节点，list1 = list1.next
否则head和end等于list2节点，list2 = list2.next

接下来继续遍历，如果list1的val小于list2的值，end.next = list1，end = end.next, list1 = list1.next
否则head和end等于list2节点，end.next = list2，end = end.next, list2 = list2.next

如果list1或者list2遍历到空了，那么就让end.next = 没空的那个链表

例如：
在这里插入图片描述

此时list1.val < list2.val，head 和 end等于list1, list1 = list1.next
在这里插入图片描述
继续比较，list2.val < list1.val, 则end.next = list2, end = end.next, list2 = list2.next

继续上述操作，直到list1或list2中有一个为空

此时list1 == null 直接让end.next = list2

最终就可以形成排序后的链表

思路一完整代码

/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Solution {public ListNode Merge(ListNode list1,ListNode list2) {if(list1 == null){return list2;}if(list2 == null){return list1;}ListNode head = null;ListNode end = head;while(list1 != null && list2 != null){if(list1.val < list2.val){if(head == null){head = list1;end = head;} else {end.next = list1;end = end.next;}list1 = list1.next;} else {if(head == null){head = list2;end = head;} else {end.next = list2;   end = end.next;}list2 = list2.next;}}if(list1 == null){end.next = list2;} else {end.next = list1;}return head;}
}

解题思路二

因为Merge返回一个排序后的链表头节点，可以使用递归的方式来解决这个问题

定义一个head头节点，如果list1.val > list2.val，那么就让head = list2, list2 = list2.next
否则head = list1, list1 = list1.next

最后递归head = Merge(list1, list2);就可以得到一个排序后的链表

而递归的出口就是当list1 == null，则直接返回list2，当list2 == null，直接返回ist1

思路二完整代码

/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Solution {public ListNode Merge(ListNode list1,ListNode list2) {//递归出口if(list1 == null){return list2;}if(list2 == null){return list1;}ListNode head = null;if(list1.val > list2.val){head = list2;list2 = list2.next;} else {head = list1;list1 = list1.next;}head.next = Merge(list1, list2);return head;}
}