合并两个有序链表(双指针)

题目

原题为LeetCode 21. 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
提示:
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

样例:
输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4]

输入:l1 = [], l2 = [] 输出:[]

输入:l1 = [], l2 = [0] 输出:[0]

思路

使用双指针思想解题

  • 首先定义两个指针p1,p2分别指向两个有序链表的头结点,定义一个指针p3始终指向新链表的最后一个节点,定义一个指针ptmp指向新链表的头结点
  • 每一次循环都比较两个指针指向节点的值,将偏小的节点加到新链表中(若相等则将p2加到新链表中),且较小的链表上的指针往后移动一位。
  • 当p1、p2任意next节点为空时,将非空节点加到新链表中。

图示为:
1.创建链表及指针


2.比较数值大小,把较小的节点加到已排序的链表

3.将p1指针向后移动

4.将p3移动到已排序链表最后一个节点

5.同步骤2

6.同步骤3

7.同步骤4

循环执行,直到一方指针为空跳出循环

非空指针指向的节点加到已排序的链表里,此时返回ptmp->next即为合并后的链表

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* p3=new ListNode(0);
        ListNode* ptmp=p3;

        while(list1 && list2)
        {
            if(list1->val < list2->val)
            {
                p3->next=list1;            
                list1=list1->next;               
            }
            else
            {
                p3->next=list2;               
                list2=list2->next;
            }
            p3=p3->next;
        }
        if(list1)
            p3->next=list1;
        else
            p3->next=list2;
        return ptmp->next;
    }
};

注意事项

注意每一步的执行顺序:将较小节点加入链表->将原链表指针向后移动->将新链表指针向后移动
此处顺序也可以改为:将较小节点加入链表->将新链表指针向后移动->将原链表指针向后移动
这两种顺序本质上并没有区别,但第一种方式实现起来更为优雅

当循环结束后,把原链表非空指针指向的节点加到已排序的链表中即可,返回虚拟头结点的next节点,即可得到合并后的有序链表

本文作者:小小黑
本文链接:https://lonelyenderman.top/archives/1048
版权声明:本站采用 BY-NC-SA 进行许可。转载请注明出处!
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(*^▽^*)
 ̄﹃ ̄
(╯‵□′)╯︵┴─┴
(~ ̄▽ ̄)~
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
( ͡° ͜ʖ ͡°)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
つ﹏⊂
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
(´▽`ʃ♡ƪ)
w(゚Д゚)w
(๑•̀ㅂ•́)و✧
(#`O′)
凸(艹皿艹 )
o(≧口≦)o
≡ω≡
(*/ω\*)
○| ̄|_
(⊙ˍ⊙)
Σ(っ °Д °;)っ
o( ̄ヘ ̄o#)
<( ̄︶ ̄)>
(。・∀・)ノ゙
(o゜▽゜)o☆
╥﹏╥
ヾ(´・ω・`)ノ
😂
😀
😅
😊
🙂
😍
😘
😜
😝
😏
😒
🙄
😳
😔
😫
😱
😭
😶
🌚
😣
🤨
😣
🤐
😪
🤤
🥵
🤮
😨
😱
😓
🤬
👴
🤡
🙈
💊
🙏
🤺
💩
👻
🙌
🖕
👍
👫
👌
🙏
👀
🐒
🔪
Source: github.com/zhheo/Sticker-Heo
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
Heo
花!
上一篇