当前位置：首页 > news >正文

合并两个有序链表——力扣21

news 2025/7/28 18:01:10

题目描述

在这里插入图片描述

法一递归

在这里插入图片描述

class Solution {
public:ListNode* mergeTwoLists(ListNode *l1, ListNode*l2){if(l1 == nullptr){return l2;} else if (l2==nullptr){return l1;} else if (l1->val<l2->val){l1->next = mergeTwoLists(l1->next, l2);return l1;} else {l2->next = mergeTwoLists(l1, l2->next);return l2;}}
};

在这里插入图片描述

法二迭代

1.使用dumy->next来保存需要返回的头结点，注意创建新结点的语法 ListNode* dummy = new ListNode(-1)
2.判断l1,l2哪个值更小，并用 pp指针来存储更小的结点指针，帮助dummy连接后，控制更小的l1,l2往后移动
直到，一边有nullptr，把另一边都接上

class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2){ListNode* dummy = new ListNode(-1);   //创建一个新的头节点 ListNode* cur = dummy;while(l1 && l2){ListNode* pp = (l1->val < l2->val) ? l1 : l2;cur->next = pp;cur = cur->next;if(pp==l1) {l1=l1->next; } else{l2 = l2->next;} }cur->next = (l1==nullptr) ? l2 : l1;ListNode* res = dummy->next;delete dummy;return res;	}//version2ListNode* mergeTwoLists(ListNode* l1, ListNode* l2){if((!l1) || (!l2)) return l1 ? l1 : l2;ListNode* dummy = new ListNode(-1);   //创建一个新的头节点 ListNode *cur=dummy, *aPtr = l1, *bPtr = l2;while(aPtr && bPtr){if(aPtr->val < bPtr->val){dummy->next = aPtr;aPtr = aPtr->next;} else {dummy->next = bPtr;bPtr = bPtr->next;}dummy = dummy->next;}dummy->next = aPtr ? aPtr : bPtr;return cur->next;	}
};