21.合并两个有序链表

发表于 | 分类于
字数统计: 382 | 阅读时长 ≈ 1

一、题目描述

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

示例：

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

二、题解

1.算法描述

  • 迭代法
  • 递归法

2.个人分析

  • 我使用的是迭代法（参考官解）

    首先，定义一个假头节点，便于将两个链表连接起来，并定义一个哨兵指针指向这个假头节点，方便我们返回最后得到的链表；

    然后，开始遍历链表一和链表二，当链表一和链表二都不为空时，pre指针总是指向val较小的节点；

    然后，pre指针始终指向所求的有序链表的最后一个节点；

    最后，将链表一和链表二中仍然不为空的链表接在最后

3.代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode *mergeTwoLists(struct ListNode *l1, struct ListNode *l2)
{
    struct ListNode *pre = (struct ListNode *)malloc(sizeof(struct ListNode));
    pre->next = NULL;
    struct ListNode *prev = pre;
    while (l1 != NULL && l2 != NULL)
    {
        if (l1->val <= l2->val)
        {
            pre->next = l1;
            l1 = l1->next;
        }
        else
        {
            pre->next = l2;
            l2 = l2->next;
        }
        pre = pre->next;//pre指针始终指向所求的有序链表的最后一个节点
    }
    pre->next = l1 == NULL ? l2 : l1;
    return prev->next;
}

三、PS

递归法不是很理解，详细请参考👉官方答案