合并两个有序链表


力扣连接:合并两个有序链表

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

链表结构定义:

public class ListNode {
   int val;
   ListNode next;
   ListNode(int x) { val = x; }
}

示例:

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

思路:这道题暴力解决的话能感觉到逻辑会较为复杂,并且代码会很乱,应该会有更优雅的方法。复杂问题要简单化递归的思路总可以拿出来套一套,看看适合不适合。不难发现要求 l1 和 l2 的合并链表,如果 l1.val <= l2.val,那么第一个节点就是 l1,而下一个节点指向 l1.next 和 l2 的合并链表即可。这不就是递归吗!

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

由之前的经验可知,递归的问题一般也可以通过迭代的方式实现,例如典型的二分查找。迭代的思想就是,使用一个 while 循环,在循环内部不断的去修改 while 的判断条件直至其退出循环,此时计算处理完成得到结果。

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);  //求新链表的问题一般都需要定义一个虚拟节点,其指向真正的头节点
        ListNode temp = prehead;  //临时节点,循环中需要不停的往后游动
        while(l1!=null || l2!=null){  //循环处理直至最后一个节点
            if(l1!=null && l2!=null){ //两个链表节点都不为空的情况,next 指向其中较小的节点
                if(l1.val <= l2.val){
                    temp.next = l1;
                    l1 = l1.next;
                }else{
                    temp.next = l2;
                    l2 = l2.next;
                }
                temp = temp.next;
            }else if(l1!=null){  //只要有其中一个链表已经遍历完,则只需要将 next 指向另一个链表剩余节点的头部即可
                temp.next = l1;
                break;
            }else{
                temp.next = l2;
                break;
            }
        }
        return prehead.next;
    }
}
Copyright © jverson.com 2019 all right reserved,powered by Gitbook 22:13:40

results matching ""

    No results matching ""