[数据结构与算法]【链表】【打卡48天】《剑指Offer》2刷：JZ16 合并两个排序的链表 ，2种方法

1、题目描述

?2、算法分析

将两个链表进行合并，而且是升序的链表。分别比较两个链表结点的值。

这里有2种方法：

①递归，不创建新的链表，直接A，B合并，不借用其他的空间

②创建新的链表，分别将A，B比较的结果进行合并

?

知识补充：括号里是头节点的值

ListNode head = new ListNode(0);此时链表中头结点的值为0

ListNode head = new ListNode(3)；此时链表中头结点的值为3

3、算法实现

方法一：创建新的链表存储

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        // 两个递增链表都不为空
        while(list1 != null && list2 != null){
            if(list1.val <= list2.val){
                cur.next = list1;
                list1 = list1.next;
            }else{
                cur.next = list2;
                list2 = list2.next;
            }
            // 当比较出来后，cur往后移动一位
            cur = cur.next;
        }
        
        // 判断其中有一个链表为空
        if(list1 != null){
            cur.next = list1;
        }
        if(list2 != null){
            cur.next = list2;
        }
        // 返回头节点的下一个结点，也就是链表的第一个结点
        return head.next;
        
    }
}

方法二：递归

/*
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;
        }
        
        if(list1.val <= list2.val){
            list1.next = Merge(list1.next,list2);
            return list1;
        }else{
            list2.next = Merge(list1,list2.next);
            return list2;
        }
    }
}