文章目錄
- 題目要求
- 方法1：使用頭指標
- 思路
- 代碼
- 方法2：使用哨兵位
- 思路
- 代碼
題目要求
鏈接：21. 合并兩個有序鏈表 - 力扣（LeetCode） (leetcode-cn.com)
方法1：使用頭指標
思路
- 假設兩個鏈表分別為l1和l2,l1和l2都是有序的
- 因為要 排成升序，把l1和l2指向的結點的較小的尾插到新鏈表
- 由于是尾插到新鏈表：為了方便，可以定義兩個指標，一個新鏈表的頭，一個指向新鏈表的尾
- 這里使用的是頭指標的寫法：
- 首先：我們應該提前把l1和l2中的較小結點，尾插下來當頭結點，更新尾指標
- 然后l1和l2繼續向后比較，找到把小的尾插下去，然后更新尾指標
- 因為總有一個鏈表先遍歷完(走到空)，把另一個沒有遍歷完的鏈表直接鏈接到尾指標后面即可(因為：l1和l2都是有序的)
- 然后回傳新鏈表的頭指標即可
**注意：**如果其中一個鏈表一開始就是空，就回傳另一個鏈表
圖解
代碼
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{
//l1為空鏈表就回傳l2
if(l1 == NULL)
{
return l2;
}
//l2為空鏈表就回傳l1
if(l2 == NULL)
{
return l1;
}
//使用頭指標
//定義頭尾指標
struct ListNode* head = NULL,*tail = NULL;
//先從l1和l2選一個小的下來作為頭，排升序
if(l1->val < l2->val)
{
//頭尾指標都要更新
head = l1;
tail = l1;
//l1更小，l1繼續往后走
l1 = l1->next;
}
else
{
//頭尾指標都要更新
head = l2;
tail = l2;
//l1小，l2繼續往后走
l2 = l2->next;
}
//遍歷比較 -如果有一個鏈表走完(空指標)就跳出回圈
while(l1 && l2)
{
if(l1->val > l2->val )
{
tail ->next = l2;//尾指標鏈接小的結點
tail = l2;//更新尾結點
l2 = l2->next;//小的結點的鏈表向后走
}
else{
tail ->next = l1;//尾指標鏈接小的結點
tail = l1;//更新尾結點
l1 = l1->next;//小的結點的鏈表向后走
}
}
//有一個結束了-未知是哪個先結束->兩個都判斷
//下面的兩個if判斷，只進入一個
if(l1)
{
tail->next = l1;//尾指標鏈接沒有比較完的鏈表
}
else{
tail->next = l2;//尾指標鏈接沒有比較完的鏈表
}
return head;//回傳新鏈表的頭指標
}
方法2：使用哨兵位
思路
和上面方法1基本一致
-
假設兩個鏈表分別為l1和l2,l1和l2都是有序的
-
使用了哨兵位，所以不需要先選一個下來當頭結點
-
由于是尾插到新鏈表：為了方便，可以定義兩個指標，一個新鏈表的頭，一個指向新鏈表的尾
-
這里使用的是哨兵位的寫法：
-
注意：哨兵位的next才是第一個結點，哨兵位不存盤有效資料
-
l1和l2從頭開始向后比較，找到把小的尾插下去，然后更新尾指標
-
-
因為總有一個鏈表先遍歷完(走到空)，把另一個沒有遍歷完的鏈表直接鏈接到尾指標后面即可(因為：l1和l2都是有序的)
-
然后回傳新鏈表的頭指標即可，回傳的是head->next才是第一個結點
注意：最后哨兵位結點要釋放掉
代碼
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
if(l1 == NULL)
{
return l2;
}
if(l2 == NULL)
{
return l1;
}
//使用哨兵位
struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* tail = head;
//遍歷比較 -如果有一個走完就跳出回圈
while(l1 && l2)
{
if(l1->val > l2->val )
{
tail->next =l2 ;
tail = tail->next;
l2 = l2->next;
}
else{
tail->next = l1;
tail = tail->next;
l1 = l1->next;
}
}
//有一個結束了
if(l1)
{
tail->next = l1;
}
else{
tail->next = l2;
}
//保存第一個結點，防止釋放掉哨兵位之后找不到
struct ListNode* tmp = head->next;
//哨兵位結點要釋放掉，然后置空
free(head);
head = NULL;
return tmp;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/387901.html
標籤：其他