1. 题目描述
2. 解题思路
与正常的合并两个有序数组思路一样,这里可以定义一个头节点(虚拟节点),可以方便我们一开始进行连接。用两个指针标记两个链表的结点,进行循环比较,谁小谁连接到我们开辟的头节点上。
最后判断谁没连接完,直接连接上就可以了。
3. 代码实现
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param pHead1 ListNode类
* @param pHead2 ListNode类
* @return ListNode类
*/
ListNode* Merge(ListNode* head1, ListNode* head2) {
if(head1 == nullptr) return head2;
if(head2 == nullptr) return head1;
ListNode* cur1 = head1, *cur2 = head2;
ListNode *head = new ListNode(-1);
ListNode *cur = head;
while(cur1 && cur2)
{
if(cur1->val < cur2->val)
{
cur->next = cur1;
cur1 = cur1->next;
}
else
{
cur->next = cur2;
cur2 = cur2->next;
}
cur = cur->next;
}
if(cur1)
cur->next = cur1;
if(cur2)
cur->next = cur2;
return head->next;
}
};