題目描述：
輸入兩個遞增的鏈表，單個鏈表的長度為n，合并這兩個鏈表并使新鏈表中的節點仍然是遞增排序的。
數據范圍： n為0~1000，節點值為-1000~1000
要求：空間復雜度 O(1)，時間復雜度 O(n)
如輸入{1,3,5},{2,4,6}時，合并后的鏈表為{1,2,3,4,5,6}，所以對應的輸出為{1,2,3,4,5,6}，轉換過程如下圖所示：
或輸入{-1,2,4},{1,3,4}時，合并后的鏈表為{-1,1,2,3,4,4}，所以對應的輸出為{-1,1,2,3,4,4}，轉換過程如下圖所示：
示例：
輸入：
{1,3,5},{2,4,6}
返回值：
{1,2,3,4,5,6}
解題思路：
本題考察數據結構鏈表的使用。有兩種解法：
- 遍歷比較。建立一個新的頭節點head后，用cur指針指向下一節點；然后依次比較兩個子鏈表節點的值大小，誰小先塞誰，塞完就將其指向下一個節點；直到某個子鏈表遍歷完，將cur的next指向沒遍歷完的那個鏈表當前的節點。
- 遞歸。從pHead1和pHead2的頭節點開始比較，誰小就返回誰，然后其下一個指向，指向Merge函數的結果，Merge輸入的兩個鏈表為小的一方的next和大的一方的頭節點，也就是用下一個值和它繼續比誰更小；依次類推，遞歸中斷的標志是有其中一個子鏈表指向nullptr，返回另一方即可。
測試代碼：
解法一，遍歷：
|
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
|
/*struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { }};*/class Solution {public: ListNode* Merge(ListNode* pHead1, ListNode* pHead2) { ListNode *head=new ListNode(-1); ListNode *cur=head; while(pHead1&&pHead2) { if(pHead1->val<=pHead2->val) { cur->next=pHead1; pHead1=pHead1->next; } else{ cur->next=pHead2; pHead2=pHead2->next; } cur=cur->next; } cur->next=pHead1?pHead1:pHead2; return head->next; }}; |
解法二，遞歸：
|
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
|
/*struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { }};*/class Solution {public: ListNode* Merge(ListNode* pHead1, ListNode* pHead2) { if(!pHead1) return pHead2; if(!pHead2) return pHead1; if(pHead1->val<=pHead2->val) { pHead1->next=Merge(pHead1->next,pHead2); return pHead1; } else{ pHead2->next=Merge(pHead1,pHead2->next); return pHead2; } }}; |
到此這篇關于C++解決合并兩個排序的鏈表問題的文章就介紹到這了,更多相關C++ 合并兩個排序的鏈表內容請搜索服務器之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持服務器之家！
原文鏈接：https://blog.csdn.net/zhaitianbao/article/details/121767253
