合并有序鏈表
- 1. 題目描述
- 2. 題目鏈接
- 3. 題目剖析
- 3.1剖析圖示
- 3.2 圖示詳解
- 4. 解題代碼
- 5. 代碼注釋詳解
滿難度系數
* * * * *，此題難度系數* * *，
滿考頻熱度* * * * *，此題熱度* * * * *，
1. 題目描述
2. 題目鏈接
- 牛客題目鏈接合并有序鏈表
3. 題目剖析
- 首先前提是兩個
有序鏈表l1,l2，將他們合并為一個有序鏈表， - 利用
歸并排序的思想，建立一個哨兵結點，每次取兩個鏈表中較小的進行合并， - 注意問題是兩個
鏈表長度可能會不一樣長，要考慮處理， - 這個題除了哨兵結點之外不要開辟另外的空間，將鏈表l1,l2從新進行有序鏈接，
哨兵結點的好處是如果兩個鏈表都為空則不需要判斷，最后回傳NewHead->next也為空，
3.1剖析圖示
3.2 圖示詳解
- 先定義一個哨兵結點，指向l1,l2里面最小的，
- 然后再找次小的進行鏈接，
- 如此迭代，直到兩個鏈表都遍歷完畢，
4. 解題代碼
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
class Solution {
public:
/**
*
* @param l1 ListNode類
* @param l2 ListNode類
* @return ListNode類
*/
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode *NewHead = new ListNode(0);//注釋1
ListNode *Node = NewHead;
//注釋2
if(l1 == nullptr)
{
return l2;
}
if(l2 == nullptr)
{
return l1;
}
//注釋3
while(l1 && l2)
{
if(l1->val < l2 ->val)
{
Node -> next = l1;
Node = Node ->next;
l1 = l1 -> next;
}
else
{
Node -> next = l2;
Node = Node -> next;
l2 = l2 ->next;
}
}
//注釋4
while(l1)
{
Node -> next = l1;
Node = Node -> next;
l1 = l1 -> next;
}
while(l2)
{
Node -> next = l2;
Node = Node -> next;
l2 = l2 ->next;
}
//注釋5
return NewHead->next;
}
};
5. 代碼注釋詳解
- 注釋1：先建立一個哨兵結點，讓最小的直接鏈接在后面，
- 注釋2：如果兩個有序鏈表中有一個為nullptr則直接回傳另外一個，
- 注釋3：兩個鏈表中有一個為空時則結束回圈，回圈內部每次找次小的結點進行鏈接，利用的是歸并排序的思想，
- 注釋4：如果兩個鏈表有一個為空，另一個還沒有為nullptr則直接將剩下的鏈接在后面，
- 注釋5：因為設立了哨兵結點，所以回傳的是哨兵結點的下一個，
合并有序鏈表演算法復雜度為：
- 時間復雜度：O(n)
- 空間復雜度：O(1)
1.如有錯誤或者沒能理解的地方，請及時評論或者私信，及時修改更新，
2.會持續更新相關鏈表高頻題目，分類專欄—資料結構，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/272336.html
標籤：其他
下一篇：純C語言實作BMP影像的讀、寫