合并两个排序的链表

Dear 丶 2024-02-19 13:38 64阅读 0赞

#### 文章目录 ####

*  题目描述
 *  代码

## 题目描述 ##

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

## 代码 ##

/*
    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;
            
            // 声名两个节点，curlist为拼接中使用的节点，mlist为指向新链表的头结点，用于返回整个新链表
            ListNode mlist = null, curlist = null;
            while(list1!=null && list2!=null) {
        
                if(list1.val<=list2.val) {
        
                    if(mlist==null) {
         // mlist为空时，首先赋初值
                        mlist = curlist = list1;
                    } else {
        
                        curlist.next = list1; // 将头结点赋给curlist的next指针
                        curlist = curlist.next; // 移动curlist到它的下一个节点
                    }
                    list1 = list1.next; // 将list1指针向后移动，指到它的下一个节点
                } else {
        
                    
                    if(mlist==null) {
        
                        mlist = curlist = list2;
                    } else {
        
                        curlist.next = list2;
                        curlist = curlist.next;
                    }
                    list2 = list2.next;
                }
            }
            
            // 判断是否list1和list2都遍历完，将没有遍历完的链表直接添加到curlist的后面
            if(list1!=null) {
        
                curlist.next = list1;
            }
            if(list2!=null) {
        
                curlist.next = list2;
            }
            
            return mlist; // 注意这里要返回mlist，这是新链表的头结点
        }
    }