剑指offer—合并两个有序链表 解答

剑指offer—合并两个有序链表

题目描述

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

思路

我们考虑到最优实现,时间复杂度应该为两个链表长度O(M+N),空间复杂度为O(1),只使用几个指针,类似归并排序思想

  • 先从第一个链表开始迭代,如果链表1当前指针的值<链表2当前指针的值则链表1指针往后移动一位,反之如果链表1当前指针的值>=链表2的值,则执行插入到链表1当前指针前面一个位置,基本代码如下:pre指向链表1当前节点的前一个节点,用于插入
ListNode next = list2.next;//保存链表2的下一个节点指针
pre.next = list2;//pre指向新插入节点
list2.next = list1;//新插入节点指向链表1当前节点
pre = list2;//更新pre到pre的下一个节点也就是新插入的节点
list2 = next;//更新链表2当前节点为下一个节点(保存的引用在这里使用)
  • 当链表1为空或者链表2为空时,结束迭代,剩下的非空链表的所有元素都大于新链表所有元素,直接接入到新链表后面就可以了,代码如下
if(list1==null&&list2!=null){//如果有一个不为空则执行连接链表操作
    list1 = list2;
    pre.next = list1;
}    

代码

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1==null||list2==null){
            return list2==null?list1:list2;
        }
        ListNode head1,head2,pre;
        head1 = list1;head2 = list2;pre = null;
        while(list1!=null&&list2!=null){
            if(list1.val>=list2.val){
                //把list2放过来
                ListNode next = list2.next;
                if(pre!=null){
                    pre.next = list2;
                }
                list2.next = list1;
                pre = list2;
                list2 = next;
            }else{
                list1 = list1.next;
                if(pre == null){
                    pre = head1;
                }else{
                    pre = pre.next;
                }
            }
        }
        if(list1==null&&list2!=null){
            list1 = list2;
            pre.next = list1;
        }
        return head2.val<=head1.val?head2:head1;
    }
}