NC33 合并两个排序的链表

题目链接：https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337

题目描述

输入两个递增的链表，单个链表的长度为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}

解题代码

import java.util.*;
/*
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 newHead = null;
        //记录新链表的尾
        ListNode newTail = null;
        //任一为空都跳出循环
        while (list1 != null && list2 != null) {
            //比较,找出比较小的节点
            ListNode tmp = list1.val < list2.val ? list1 : list2;
            //节点较小的链表向下走一步
            if (tmp == list1) {
                list1 = list1.next;
            } else {
                list2 = list2.next;
            }
            //第一次插入
            if (newHead == null) {
                newHead = tmp;
                newTail = tmp;
            } else {
                //不是第一次插入
                newTail.next = tmp;
                newTail = newTail.next;
            }
        }
        //任一链表为空,新链表连接不为空的链表
        if (list1 == null) {
            newTail.next = list2;
        } else {
            newTail.next = list1;
        }
        return newHead;
    }
}

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名，转载请...
最后编辑时间为: 2022/07/14 15:32:58