专栏首页aCloudDeveloperLeetCode:21_Merge Two Sorted Lists | 合并两个排序列表 | Easy

LeetCode:21_Merge Two Sorted Lists | 合并两个排序列表 | Easy

题目:Merge Two Sorted Lists

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

简单题,只要对两个链表中的元素进行比较,然后移动即可,只要对链表的增删操作熟悉,几分钟就可以写出来,代码如下:

 1 struct ListNode {
 2     int val;
 3     ListNode *next;
 4     ListNode(int x):val(x), next(NULL) {}
 5 };
 6 
 7 ListNode *GetLists(int n)    //得到一个列表
 8 {
 9     ListNode *l = new ListNode(0);
10     ListNode *pre = l;
11     int val;
12     for (int i = 0; i < n; i ++) {
13         cin >> val;
14         ListNode *newNode = new ListNode(val);
15         pre->next = newNode;
16         pre = pre->next;
17     }
18     return l->next;
19 }
20 
21 ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
22 {
23     assert (NULL != l1 && NULL != l2);
24     if (NULL == l1 && NULL == l2)
25         return NULL;
26     if (NULL == l1 && NULL != l2) // !!要记得处理一个为空,另一个不为空的情况
27         return l2;
28     if (NULL != l1 && NULL == l2)
29         return l1;
30     
31     ListNode *temp = new ListNode(0);
32     temp->next = l1;
33     ListNode *pre = temp;
34 
35     while(NULL != l1 && NULL != l2) {
36         if (l1->val > l2->val) { //从小到大排列
37             ListNode *next = l2->next;
38             l2->next = pre->next;
39             pre->next = l2;
40             l2 = next;
41         }        
42         else {
43             l1 = l1->next;
44         }
45         pre = pre->next;
46     }
47     if (NULL != l2) {
48         pre->next = l2;
49     }
50     return temp->next;
51 }

这其中要注意一点,即要记得处理一个链表为空,另一个不为空的情况,如{}, {0} -- > {0},当然上面的写法多少啰嗦了一些,可以简写。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode: 2_Add Two Numbers | 两个链表中的元素相加 | Medium

    题目: You are given two linked lists representing two non-negative numbers. The di...

    CloudDeveloper
  • Leetcode:148_Sort List | O(nlogn)链表排序 | Medium

    题目:Sort List Sort a linked list in O(n log n) time using constant space complexi...

    CloudDeveloper
  • CPU 虚拟化

    前面 虚拟化技术总览 中从虚拟平台 VMM 的角度,将虚拟化分为 Hypervisor 模型和宿主模型,如果根据虚拟的对象(资源类型)来划分,虚拟化又可以分为计...

    CloudDeveloper
  • LeetCode Add Two Numbers

    You are given two non-empty linked lists representing two non-negative integers....

  • LeetCode 21 Merge Two Sorted Lists

    ShenduCC
  • Leetcode2——Add Two Numbers

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • 【LeetCode】2. Add Two Numbers

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • macOS下GDAL Java开发环境搭建

    今天在笔记本(macOS平台)上折腾了一下如何搭建GDAL的Java开发环境。虽然GDAL的Python接口更好用,但是有时候需要协同使用一些Java库的时候,...

    卡尔曼和玻尔兹曼谁曼
  • 你知道有几种方式来判断JS的数据类型吗?

    因为JavaScript是一门弱引用类型的语言,所以在开发过程中我们常常会遇到 “我定义的这个变量是什么数据类型?”这种类似的问题,所以今天我们来看看在JS中一...

    用户2802329
  • 万能 Java

    三哥

扫码关注云+社区

领取腾讯云代金券