题目描述

输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。

数据范围

链表长度 [0,500]。

解题思路

两个链节相互连接,需要构造一个虚拟头节点(只能写virtu,virtual是虚函数关键词),同时创造节点需要初始化指针
然后对链节操作的时候都需要检查链表是否为空这里while就是(l1&&l2是判断是否为空)注意输入和比较是同步的
在循环里面比较l1和l2的大小,如果前者小,ptr的next指针指向l1,l1后移一位,此时出现一个虚拟空位,ptr指针后移依次遍历.最后if条件句判断有无剩余节点,有的话移动到l1的位置

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode *virtu = new ListNode(-1);  // 创建一个虚拟头结点
        ListNode *ptr = virtu;  // 初始化指针
        while(l1 && l2){  // 当两个链表都不为空时
            if(l1->val <= l2->val){  
                ptr->next = l1; 
                ptr = ptr->next;  
                l1 = l1->next;  
            } else {
                ptr->next = l2; 
                ptr = ptr->next;  
                l2 = l2->next;  
            }
        }
        if(l1){  // 如果l1还有剩余节点（即l2已经遍历完了，但l1还有剩余）
            ptr->next = l1;  // 连接到ptr的后面
            ptr = ptr->next;  // 移动ptr到l1的位置
        } else {  // 如果l2还有剩余节点（即l1已经遍历完了，但l2还有剩余）
            ptr->next = l2;  // 连接到ptr的后面
            ptr = ptr->next;  // 移动ptr到l2的位置
        }
        return virtu->next;  // 返回合并后的链表的头结点
    }    
};

篇章

上一篇:AcWing 28. 在O(1)时间删除链表结点
https://www.acwing.com/solution/content/211895/
下一篇:AcWing 78. 左旋转字符串
https://www.acwing.com/solution/content/211945/