剑指Offer-合并两个排序的链表

绝地灬酷狼 2022-08-04 12:50 120阅读 0赞

**合并两个排序的链表**

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

解题思路：  
  其实就是采用比较大小，然后使用尾插法进行构建合并链表。

我的Java代码如下：

/*
    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(null==list1){
                return list2;
            }
            if(null == list2){
                return list1;
            }else{
                ListNode head = null;
                if(list1.val < list2.val){
                    head = new ListNode(list1.val);
                    list1 = list1.next;
                }else{
                    head = new ListNode(list2.val);
                    list2 = list2.next;
                }
                ListNode list = head;
                while(null != list1 && null != list2){
                    if(list1.val < list2.val){
                        list.next = new ListNode(list1.val);
                        list1 = list1.next;
                    }else{
                        list.next = new ListNode(list2.val);
                        list2 = list2.next;
                    }
                    list = list.next;
                }
    
                if(null==list1){
                    list.next = list2;
                }
                if(null == list2){
                    list.next = list1;
                }
    
                return head;
    
            }
        }
    }