合并两个排序的链表（剑指offer 25）Java

合并两个排序的链表（剑指offer 25）Java

目录

一、题目描述

二、思路讲解

三、Java代码实现 

四、时空复杂度分析 

---

 

一、题目描述

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

示例1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

限制：

0 <= 链表长度 <= 1000

二、思路讲解

        两个指针分别从两个链表的头出发， 哪个节点的值小，就把他加到公共节点的后面。等某一个链表遍历完之后，就把没遍历完的链表直接放到公共链表的后面。

        由于题目中并没有给出公共链表的头结点，我们可以随意申请一个节点head，将他作为公共链表的头， *** 作完成后直接返回head.next即可。

三、Java代码实现 

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        ListNode head = new ListNode(0);    //申请头结点
        ListNode p = head;  //指针，初始化指向公共链表头结点

        //一旦有一个链表为空，跳出
        while(l1!=null && l2!=null){
            if(l1.val <= l2.val){
                //保存l1的后面部分
                ListNode next = l1.next;
                p.next = l1;
                p.next.next = null;
                p = p.next;
                l1 = next;
            } else {
                ListNode next = l2.next;
                p.next = l2;
                p.next.next = null;
                p = p.next;
                l2 = next;
            }
        }

        //将剩余部分加到公共指针后面
        if(l1!=null){
            p.next = l1;
        }
        if(l2!=null){
            p.next = l2;
        }

        return head.next;
    }

}

四、时空复杂度分析 

        时间复杂度：        O（M+N）        需要遍历两个链表

        空间复杂度：        O（1）             只额外申请了一个头结点和一个指针