合并两个有序链表

LonelyEnderman

发布于 2023-08-11 15:51:46

1660

发布于 2023-08-11 15:51:46

文章被收录于专栏：小小黑的游戏开发之路小小黑的游戏开发之路

题目

原题为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;
    }
};