leetcode 鏈表的合并和分割兩道題
- 1.合并兩個有序鏈表
- 1.1 題目描述
- 1.2 介面函式
- 1.3 大致框架
- 1.3.1 思路分析
- 1.3.2 具體步驟
- 1.4 具體實作
- 1.5 方法選擇
- 2. 分割鏈表
- 2.1 題目描述
- 2.2 介面函式
- 2.3 大致框架
- 2.3.1 思路分析
- 2.3.2 具體步驟
- 2.4 具體實作
1.合并兩個有序鏈表
1.1 題目描述
本題目來源于leetcode 21.合并兩個有序鏈表
提示：
1.2 介面函式
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
}
1.3 大致框架
1.3.1 思路分析
- 新建立一個鏈表，即建立一個頭結點
這里我們要有2個指標，分別都指空
- 為什么要一個head，因為要回傳頭指標
- 為什么要一個tail，因為要方便尾插
- 然后陣列上下兩兩比較，小的就依次放在新鏈表
比較是用一個
L1和一個L2指標分別指向原來兩個鏈表的頭節點
l1指向下一個指標然后新鏈表的head不動，tail指標指向這一個節點，即叫做尾指標的意思
- 不斷回圈，最后當其中一個鏈表的L1或L2指標指向NULL時，就停止回圈
- 最后將剩下來的一個鏈表連接在新鏈表后面就可以了
1.3.2 具體步驟
先要防止傳進來的而指標是空的
//注意第一次凡是有空指標也會崩
//如果為空直接回傳另外一個就可以了
if(l1==NULL)
{
return l2;
}
if(l2==NULL)
{
return l2;
}
這里，頭插最好不要放在while回圈里面，在回圈之前解決掉就可以了
if(l1->val<l2->val)
{
head=tail=l1;
l1=l1->next;
}
else
{
head=tail=l2;
l2=l2->next;
}
while回圈不斷走直到最后走到由一個指標NULL
while(l1&&l2)
{
//取小的尾插到新鏈表
if(l1->val<l2->val)
{
tail->next=l1;
l1=l1->next;
}
else
{
tail->next=l2;
l2=l2->next;
}
//tail走到新的位置上
tail=tail->next;
}
當由一個為空時把另外一個連到新鏈表上然后，回傳頭指標
//l2為空
if(l1)
{
tail->next=l1;
}
//l1為空
if(l2)
{
tail->next=l2;
}
return head;
1.4 具體實作
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
//注意第一次凡是有空指標也會崩
if(l1==NULL)
{
return l2;
}
if(l2==NULL)
{
return l1;
}
struct ListNode* head=NULL;
struct ListNode* tail=NULL;
//第一次不要放在回圈里面
if(l1->val<l2->val)
{
head=tail=l1;
l1=l1->next;
}
else
{
head=tail=l2;
l2=l2->next;
}
while(l1&&l2)
{
//取小的尾插到新鏈表
if(l1->val<l2->val)
{
tail->next=l1;
l1=l1->next;
}
else
{
tail->next=l2;
l2=l2->next;
}
//tail走到新的位置上
tail=tail->next;
}
//l2為空
if(l1)
{
tail->next=l1;
}
//l1為空
if(l2)
{
tail->next=l2;
}
return head;
}
1.5 方法選擇
另一個帶頭節點法：
-
設定一個哨兵位頭節點
-
一樣的判斷步驟，進行尾插
這里不能忘記==
tail->next=NULL;==避免兩個都是空的
-
剩下的步驟同樣道理，主要是少一點開始的判斷步驟
-
注意最后要處理釋放之前的節點
//創建一個哨兵位頭節點
struct ListNode* head=NULL;
struct ListNode* tail=NULL;
head =tail=(struct ListNode*)malloc(sizeof(struct ListNode));
tail->next=NULL;//防止兩個都是空的，方便尾插
while(l1&&l2)
{
//取小的尾插到新鏈表
if(l1->val<l2->val)
{
tail->next=l1;
l1=l1->next;
}
else
{
tail->next=l2;
l2=l2->next;
}
tail=tail->next;
}
//l2為空
if(l1)
{
tail->next=l1;
}
//l1為空
if(l2)
{
tail->next=l2;
}
struct ListNode* node=head;
head=head->next;
free(node);
return head;
2. 分割鏈表
2.1 題目描述
這是遇到的第一道難度為中等的題
本題目來源于leetcode 分割鏈表
提示：
2.2 介面函式
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* partition(struct ListNode* head, int x){
}
2.3 大致框架
假如給出這樣的例子，雖說原題沒有要求說順序不變，但是這里用牛客網的要求做試試看
那么這時我們的答案應該是，因為要求了相對順序是不能變的，所以最后輸出就是這樣
2.3.1 思路分析
把小于x的尾插到一個鏈表，再把大于x的尾插到一個鏈表，最后連接兩個鏈表
- 創建兩個哨兵位的頭節點，分別創建對應的頭尾指標
- 分別判斷假如該節點的值小于給出的x，就尾插到小數鏈表，反之大的鏈表
- 當然尾指標要自動跟上，變成尾，走完后會發現大致順序沒有變化
- 最后來鏈接在一起就ok了，終止條件是原鏈表走完
2.3.2 具體步驟
按照第一次的思路按部就班地做
出現了問題，提示
struct ListNode* partition(struct ListNode* head, int x){
struct ListNode* lessHead,*lessTail,*greaterHead,*greaterTail;
lessHead=lessTail=(struct ListNode*)malloc(sizeof(struct ListNode));
greaterHead=greaterTail=(struct ListNode*)malloc(sizeof(struct ListNode));
lessTail->next=NULL;
greaterTail->next=NULL;
struct ListNode*cur=head;
while(cur)
{
if(cur->val<x)//只處理<的
{
lessTail->next=cur;
lessTail=lessTail->next;
}
else
{
greaterTail->next=cur;
greaterTail=greaterTail->next;
}
cur=cur->next;
}
//連接兩個鏈表
lessTail->next=greaterHead->next;
head=lessHead->next;
free(lessHead);
free(greaterHead);
return head;
}
這樣說明出現問題，就要改進一下
一般時間超限原因是出現死回圈
記憶體超限有時候是因為其他原因導致，這道題不是因為這里超過記憶體復雜度問題，應該想一下極端情況
這個情況是很難想到的，需要多多體會
我們將 greater 的 next指標置空，這是因為當前節點復用的是原鏈表的節點，而其 next指標可能指向一個小于 x 的節點，這樣就會形成環，我們需要切斷這個參考，
正是因為死回圈所以才會報錯
解決方法就是把最后一個節點置空
//關鍵
greaterTail->next=NULL;
2.4 具體實作
struct ListNode* partition(struct ListNode* head, int x){
struct ListNode* lessHead,*lessTail,*greaterHead,*greaterTail;
lessHead=lessTail=(struct ListNode*)malloc(sizeof(struct ListNode));
greaterHead=greaterTail=(struct ListNode*)malloc(sizeof(struct ListNode));
lessTail->next=NULL;
greaterTail->next=NULL;
struct ListNode*cur=head;
while(cur)
{
if(cur->val<x)//只處理<的
{
lessTail->next=cur;
lessTail=lessTail->next;
}
else
{
greaterTail->next=cur;
greaterTail=greaterTail->next;
}
cur=cur->next;
}
//連接兩個鏈表
lessTail->next=greaterHead->next;
//關鍵
greaterTail->next=NULL;
head=lessHead->next;
free(lessHead);
free(greaterHead);
return head;
}
小結：
這道題其實還有多種解法,有興趣可以看一下多題解
這篇題目就到此為止，大家覺得有識訓就請一鍵三連，謝謝
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/350933.html
標籤：其他
上一篇：Linux開發工具
下一篇：劍指offer-之-鏈表