算法-java

题目来自牛客网

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

数据范围： 0≤𝑛≤10000≤n≤1000，−1000≤节点值≤1000−1000≤节点值≤1000
要求：空间复杂度 𝑂(1)O(1)，时间复杂度 𝑂(𝑛)O(n)

如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead1 ListNode类 
     * @param pHead2 ListNode类 
     * @return ListNode类
     */
    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        // write code here
        if(pHead1 == null) return pHead2;
        if(pHead2 == null) return pHead1;
        ListNode res =new ListNode(0);
        ListNode p=res;
        while(pHead1 !=null && pHead2!=null){
            if(pHead1.val <=pHead2.val){
                res.next =pHead1;
                pHead1=pHead1.next;
            }else{
                res.next=pHead2;
                pHead2=pHead2.next;
            }
            res=res.next;
        }
        if(pHead1==null){
            res.next=pHead2;
        }else{
            res.next=pHead1;
        }
        return p.next;
    }
}

这段代码实现了将两个有序链表合并为一个有序链表的功能。下面是对这段代码的解析：

1. 首先判断两个输入链表是否为空，如果其中一个为空，则直接返回另一个链表。
2. 创建一个新的链表头节点 res，并用指针 p 指向该头节点，用于构建合并后的链表。
3. 使用 while 循环，遍历两个输入链表，直到其中一个链表为空。
4. 在循环中，比较当前两个链表节点的值，将较小的节点接到 res 节点后面，并将指针移动到下一个节点。
5. 循环结束后，将剩余的非空链表直接接到 res 节点后面。
6. 返回合并后的链表的头节点，即 res 的下一个节点。

这段代码的时间复杂度为 O(m + n)，其中 m 和 n 分别是两个输入链表的长度。因为只需要遍历一遍两个链表即可完成合并操作，所以时间复杂度是线性的。