刷题21.两个有序链表合并为一个新的有序链表

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

示例1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
限制：0 <= 链表长度 <= 1000

1. 循环法

一个元素一个元素比较，比较后按照大小结果判断下一个比较

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            
            //保存新和并排序好的链表（头结点）
            ListNode resultNode = new ListNode();
            //尾节点来增加数据
            ListNode tail = resultNode;
            while(l1 != null && l2 != null){
                if(l1.val < l2.val){
                    tail.next = l1;
                    l1 = l1.next;
                    tail = tail.next;
                }else{
                    tail.next = l2;
                    l2 = l2.next;
                    
                    tail = tail.next;
                }
            }
            if(l1 == null){
                tail.next = l2;
            }
            if(l2 == null){
                tail.next = l1;
            }
            //最终返回的是头节点的下一个节点开始的链表,因为最初的头节点不是我们需要合并的数据  
            return resultNode.next;
    }
}

2. 递归法


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        
        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }
        if(l1.val > l2.val){
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }else{
            l1.next = mergeTwoLists(l1.next,l2);
            return l1;
        }
            
    }
}

这样写可能会比较好理解一些

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        
        ListNode head = new ListNode();
        //递归出口1,当一直往下面比较的时候，如果出现其中一个已经没有元素了，那么直接将剩下的链表接到排序好的链表的后面
        if(l1 == null){
            return l2;
        }
        //递归出口2
        if(l2 == null){
            return l1;
        }
        if(l1.val > l2.val){
            head = l2;
            head.next = mergeTwoLists(l1,l2.next);
        }else{
            head = l1;
            head.next = mergeTwoLists(l1.next,l2);
        }
        return head;
            
    }
}

下面这张图可以帮助你理解递归

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: 2021/05/17 00:17