BM4 合并两个排序的链表

题目描述

描述

描述

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

数据范围：0≤n≤1000， 0≤节点值≤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}

解题思路

解法1 利用哑结点

1.使用哑结点，遍历list1、list2

2.如果list1.val < list2.val，则采用list1当前节点，并且移动到下一位，否则为list2的当前节点

3.直到list1或者list2为空，把剩余节点，遍历完成即为所求结果

4.此时哑结点的下一节点，即为所求结果

解法2 空间复杂度为O（1）的解法

使用哑结点的解法，时间复杂度和空间复杂度都是O（n），题目要求，空间复杂度需要为O（1）

1.想到了在list当前链表，直接操作的解法

2.直接比较当前节点值list1.val < list2.val，则继续遍历list1，否则将list2的当前节点，插入到list1当前节点中

3.重复步骤2，直到移动到list1或者list2末尾

实践代码

解法 1 代码

import java.awt.List;

/*
public class ListNode {
    int val;
    ListNode next = null;

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

        while (list1 != null) {
            node.next = new ListNode(list1.val);
            list1 = list1.next;
            node = node.next;
        }

        while (list2 != null) {
            node.next = new ListNode(list2.val);
            list2 = list2.next;
            node = node.next;
        }
        
        return res.next;
    }
}

解法2 代码

import java.awt.List;

/*
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;
        }
        return list1.val < list2.val ? mergetListNode(list1, list2) : mergetListNode(list2, list1);
    }

    private ListNode mergetListNode(ListNode list1, ListNode list2) {
        ListNode res = list1;
        ListNode pre = list1;
        list1 = list1.next;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                list1 = list1.next;
                pre = pre.next;
            } else {
                pre.next = new ListNode(list2.val);
                pre.next.next = list1;
                pre = pre.next;
                list2 = list2.next;
            }
        }

        if (list2 != null) {
            pre.next = list2;
        }
        return res;
    }
}