​LeetCode刷题实战21:合并两个有序链表

程序IT圈

共 966字,需浏览 2分钟

 ·

2020-08-28 13:21

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !


今天和大家聊的问题叫做合并两个有序链表,我们先来看题面:

https://leetcode-cn.com/problems/merge-two-sorted-lists/

Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.

题意


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

样例


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

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

题解

两个有序链表的排序,实际上可以看成一个单链表使用归并排序的最后一个环节:“将两个排好序的子序列合并为一个子序列:每次都是从未比较的两个子序列的最小值中选出一个更小值”。

/**
 * 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 temp=new ListNode(0);
        ListNode head=temp;//保留头节点的引用
        while(l1!=null&&l2!=null){
           if(l1.val           {
               temp.next=l1;
               l1=l1.next;
           }
           else
           {
               temp.next=l2;
               l2=l2.next;
           }
           temp=temp.next;
        }
        if(l1==null) temp.next=l2;//l1子序列为空,则直接拼届l2
        if(l2==null) temp.next=l1;
        return head.next;//返回头节点指向的序列
    }
}

本题还有其他的解法,没有一一介绍,大家可以去LeetCode上学习一下 。
好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力。

上期推文:


LeetCode刷题实战1:在数组上遍历出花样

LeetCode刷题实战2:用链表模拟加法

LeetCode刷题实战3:最长不重复子串

LeetCode刷题实战4:两个正序数组的中位数

LeetCode刷题实战5:判断回文子串

LeetCode刷题实战6:Z字形变换

LeetCode刷题实战7:整数反转

LeetCode刷题实战8:字符串转换整数

LeetCode刷题实战9:求解回文数

LeetCode刷题实战10:字符串正则匹配

LeetCode刷题实战11: 盛最多水的容器

LeetCode刷题实战12: 整数转罗马数字

LeetCode刷题实战13: 罗马数字转整数

LeetCode刷题实战14: 最长公共前缀

LeetCode刷题实战15:三数之和

LeetCode刷题实战16: 最接近的三数之和

LeetCode刷题实战17: 电话号码的字母组合

LeetCode刷题实战18: 四数之和

LeetCode刷题实战19:删除链表的倒数第N个节点

LeetCode刷题实战20:有效括号


浏览 23
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报