合并两个排序的链表

叁歲伎倆 2022-06-08 01:11 183阅读 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) // list1为空,直接返回list2
                return list2;
            if(list2 == null) // list2为空，直接返回list1
                return list1;
    
            ListNode mergeHead = null; // 定义合并结果的链表头
            ListNode current = null; // 定义中间的临时结点
            while(list1 != null && list2 != null){
                if(list1.val <= list2.val){ //list1的值小于list2的值，临时结点指向list1
                    if(mergeHead == null){
                        mergeHead = current = list1;
                    }else{
                        current.next = list1;
                        current = current.next;
                    }
                    list1 = list1.next; // list1向后移动
                }else{  //list2的值小于list1的值，临时结点指向list2
                    if(mergeHead == null){
                        mergeHead = current = list2;
                    }else{
                        current.next = list2;
                        current = current.next;
                    }
                    list2 = list2.next; // list2向后移动
                }
            }
            if(list1 == null){ //list1已到尾结点，list2剩下的直接合并
                current.next = list2;
            }else{  // list2已到尾结点，list1剩下的直接合并
                current.next = list1;
            }
            return mergeHead;
        }
    }

### 方法二，递归的方法 ###