Leetcode刷题java之21. 合并两个有序链表（递归和迭代）

拼搏现实的明天。 2024-04-17 05:25 53阅读 0赞

题目：

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4  
输出：1->1->2->3->4->4

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

### **迭代：** ###

执行结果：

通过

显示详情

执行用时 :1 ms, 在所有 Java 提交中击败了99.79%的用户

内存消耗 :36.4 MB, 在所有 Java 提交中击败了87.29%的用户

思路：

采用迭代的方式一般都会返回头节点，所以我们先用一个head来记录头结点，然后利用一个与它最开始相同的pre来进行迭代，最后返回头节点就可以了。在链表的迭代算法基本上都会创建一个pre来记录上一个节点。

代码：

/**
     * 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(0);
            ListNode pre=head;
            while(l1!=null&&l2!=null)
            {
                if(l1.val<l2.val)
                {
                    pre.next=l1;
                    l1=l1.next;
                }else
                {
                    pre.next=l2;
                    l2=l2.next;
                }
                pre=pre.next;
            }
            pre.next=l1==null?l2:l1;
            return head.next;
        }
    }

### 递归： ###

执行结果：

通过

显示详情

执行用时 :1 ms, 在所有 Java 提交中击败了99.79%的用户

内存消耗 :36 MB, 在所有 Java 提交中击败了87.48%的用户

思路：

递归不断深入，每次都返回当前的节点，并且还得考虑到哪一个链表先为空的问题。

代码:

/**
     * 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)
            {
                l1.next=mergeTwoLists(l1.next,l2);
                return l1;
            }else
            {
                l2.next=mergeTwoLists(l1,l2.next);
                return l2;
            }
        }
    }