C++解決合並兩個排序的鏈表問題

題目描述:

輸入兩個遞增的鏈表,單個鏈表的長度為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}

解題思路:

本題考察數據結構鏈表的使用。有兩種解法:

  1. 遍歷比較。建立一個新的頭節點head後,用cur指針指向下一節點;然後依次比較兩個子鏈表節點的值大小,誰小先塞誰,塞完就將其指向下一個節點;直到某個子鏈表遍歷完,將cur的next指向沒遍歷完的那個鏈表當前的節點。
  2. 遞歸。從pHead1和pHead2的頭節點開始比較,誰小就返回誰,然後其下一個指向,指向Merge函數的結果,Merge輸入的兩個鏈表為小的一方的next和大的一方的頭節點,也就是用下一個值和它繼續比誰更小;依次類推,遞歸中斷的標志是有其中一個子鏈表指向nullptr,返回另一方即可。

測試代碼:

解法一,遍歷:

/*
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;
    }
};

解法二,遞歸:  

/*
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++ 合並兩個排序的鏈表內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!

推薦閱讀: