牛客网高频算法题系列-BM4-合并两个排序的链表
题目形容
输出两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点依然是递增排序的。
- 数据范畴： 0 <= n <= 1000，-1000 <= 节点值 <= 1000
- 要求：空间复杂度 O(1)，工夫复杂度 O(n)
原题目见：BM4 合并两个排序的链表
解法一：链表遍历
- 首先，判断非凡状况，如果链表一为空，间接返回链表二；如果链表二为空，间接返回链表一。
否则，先申明一个新的假头结点，而后遍历链表一和链表二，过程如下：
- 如果链表一为空，间接将链表二剩下的结点接到前面，并终止遍历
- 如果链表二为空，间接将链表一剩下的结点接到前面，并终止遍历
- 否则，比拟链表一和链表二以后结点的大小，来判断下一个结点，而后解决下一个结点
- 最初，返回合并后的链表。
代码
public class Bm004 { /** * 合并两个排序的链表 * * @param list1 链表一 * @param list2 链表二 * @return */ public static ListNode merge(ListNode list1, ListNode list2) { // 如果链表一为空，间接返回链表二 if (list1 == null) { return list2; } // 如果链表二为空，间接返回链表一 if (list2 == null) { return list1; } // 申明一个新的假头结点 ListNode newList = new ListNode(-1), next = newList; // 遍历链表一和链表二 while (list1 != null || list2 != null) { if (list1 == null) { // 如果链表一为空，间接将链表二剩下的结点接到前面，并终止遍历 next.next = list2; break; } else if (list2 == null) { // 如果链表二为空，间接将链表一剩下的结点接到前面，并终止遍历 next.next = list1; break; } else if (list1.val < list2.val) { // 否则，比拟链表一和链表二以后结点的大小，来判断下一个结点，而后解决下一个结点 next.next = list1; list1 = list1.next; } else { next.next = list2; list2 = list2.next; } next = next.next; } // 最初，返回合并后的链表 return newList.next; } public static void main(String[] args) { // 1 -> 3 -> 5 ListNode list1 = ListNode.testCase3(); System.out.println("链表一"); ListNode.print(list1); // 2 -> 4 -> 6 ListNode list2 = ListNode.testCase4(); System.out.println("链表二"); ListNode.print(list2); ListNode newList = merge(list1, list2); System.out.println("合并后的链表"); ListNode.print(newList); }}$1.01^{365} ≈ 37.7834343329$
$0.99^{365} ≈ 0.02551796445$
置信保持的力量！