反轉鏈表
? 題目鏈接點這里
三指標：
? 解題思路：
-
先分析特殊情況，當鏈表為慷訓者只有一個結點時，直接回傳head即可
-
當鏈表的結點多于一個時，我們首先考慮到是否可以將指標的指向依次反過來，從而實作鏈表的反轉，如下圖：
那么要將指標的指向反轉過來，可以先定義兩個指標n1和n2
n2->next=n1;但這里有個問題，當n2指向n1時，第二個結點的地址丟失了，因此，還要多定義一個指標n3用于保存第二個結點的地址
-
當實作第一個結點指向NULL后，n1，n2，n3均向后移動一個結點，使第二個結點指向第一個結點
這里三個指標的移動使用迭代完成，總共分為三步：
- n1=n2
- n2=n3
- n3=n3->next
-
重復第三步，直至n2指向NULL時，回圈結束，反轉鏈表完成
這里要特別注意的是，由于是現在進行反轉，在迭代，因此當n3指向NULL時，還要進行一次迭代，回圈才會結束
完整代碼
struct ListNode* reverseList(struct ListNode* head){ if(head==NULL||head->next==NULL) return head; struct ListNode* n1=NULL,*n2=head,*n3=head->next; while(n2) { n2->next=n1; n1=n2; n2=n3; if(n3) n3=n3->next; } return n1; }
頭插法：
? 解題思路：
-
除了從原來的鏈表上實作反轉，還可以新開辟一個鏈表，指標newhead指向表頭，利用頭插法，依次將原來鏈表的結點頭插到新的鏈表中
struct ListNode* newhead = NULL; -
先定義兩個指標cur和next，cur用于從舊鏈表中取結點頭插在新鏈表中,next同于保存下一個結點，以防cur將結點移動到新鏈表后，無法重新找到舊鏈表
-
當cur==NULL時，鏈表完成反轉，具體程序如下：
完整代碼
struct ListNode* reverseList(struct ListNode* head){ struct ListNode* newhead = NULL; //開辟新鏈表 struct ListNode* cur = head; //cur用于從舊鏈表中取結點頭插在新鏈表中 while(cur) //cur不為NULL時，回圈繼續 { struct ListNode* next=cur->next; //用于保存cur移動結點的下一個結點 cur->next=newhead; //頭插到新鏈表中 newhead=cur; //newNode指向新鏈表中新的頭結點 cur=next; //cur回到舊鏈表中，繼續移動下一個結點 } return newhead; }
鏈表的中間節點
? 題目鏈接點這里
? 解法：快慢指標
- 根據題目的意思，可知遍歷鏈表后，需回傳中間結點
- 那么是否可以定義兩個指標，當快的指標遍歷結束后，慢的指標恰好指向鏈表的中間結點
- 不難發現，只要快的指標每次比慢的指標多走一步，結束時，慢的指標就能指向鏈表的中間結點
完整代碼
struct ListNode* slow=head;
struct ListNode* fast=head; //快慢指標起始位置均指向頭結點
//當fast==NULL（結點個數為奇數），fast->next==NULL(結點個數為偶數)，回圈結束，找到中間結點
while(fast&&fast->next)
{
slow = slow->next;
fast = fast->next->next; //慢指標走一步，快指標走兩步
}
return slow;
鏈表中倒數第k個節點
? 題目： 輸入一個鏈表，輸出該鏈表中倒數第k哥結點，為了符合大多數人的習慣，本題從1開始計數，即 鏈表的尾結點是倒數第1個結點，例如一個鏈表有6個結點，從頭結點開始它們的值依次是1，2，3，4， 5，6，這個鏈表的倒數第3個結點是值為4的結點，
? 解題思路：
- 這題和上一題一樣，也是要求回傳鏈表中的某個結點，因此，同樣可以用快慢指標的方法來解決
- 定義快慢指標，但這里稍微不同的是快指標起始位置指向NULL，慢指標指向頭結點，快指標提前走k步，然后快慢指標再同時向前移動，那么快指標將一直領先慢指標k個節點，在快指標遍歷鏈表后，慢指標指向的結點就是鏈表中倒數第k個結點，
struct ListNode*fast=NULL; //快指標指向NULL
struct ListNode*slow=pHead; //慢指標指向頭結點
while(k--) //快指標先走k步
{
if(fast)
fast=fast->next;
else
return NULL;
}
while(fast) //快慢指標同時移動
{
fast=fast->next;
slow=slow->next;
}
return slow;
合并兩個有序鏈表
題目鏈接點這里
-
首先考慮特殊情況，若鏈表都為空則回傳其中一個鏈表即可，若其中一個為空，則回傳另一個不為空的鏈表
if(list1==NULL) { return list2; } if(list2==NULL) { return list1; } -
除了第一種特殊情況外，其他情況可以malloc一個帶哨兵位的頭結點，依次比較list1和list2的結點大小，小的結點優先尾插到新鏈表，要進行尾插，則要定義一個指向新鏈表尾結點的指標，記錄尾結點的地址
Node*head=NULL,*tail=NULL; head=tail=(Node*)malloc(sizeof(Node)); //取小的尾插 while(list1&&list2) { if(list1->val<list2->val) { tail->next=list1; list1=list1->next; } else { tail->next=list2; list2=list2->next; } tail=tail->next; } -
何時結束？當其中一個鏈表為空時，將另一個鏈表的剩余部分整體尾插到新鏈表之后即可
if(list1) tail->next=list1; else tail->next=list2;
? 整體流程如下：
? 
完整代碼
typedef struct ListNode Node;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
if(list1==NULL) //特殊情況判斷
{
return list2;
}
if(list2==NULL)
{
return list1;
}
Node*head=NULL,*tail=NULL;
//帶哨兵位的頭結點，不儲存有效資料
head=tail=(Node*)malloc(sizeof(Node));
//取小的尾插
while(list1&&list2) //兩個鏈表均不為空
{
if(list1->val<list2->val)
{
tail->next=list1;
list1=list1->next;
}
else
{
tail->next=list2;
list2=list2->next;
}
tail=tail->next;
}
if(list1)
tail->next=list1;
else
tail->next=list2;
Node *realHead;
realHead=head->next; //真正的頭結點是哨兵位的下一個結點
return realHead;
}
鏈表分割
題目鏈接點這里
思路：
由于在原來鏈表的基礎上無法對鏈表進行重新排序，那么既然題目要求將比x大的移到x結點之后，比x小的移到x結點之前，我們可以開辟兩個鏈表，一個用來儲存比x小的結點（smallhead），一個用來儲存比x大的結點（bighead)，然后將兩個鏈表連接起來即可，
- 遍歷原鏈表，比x小的結點尾插到smallhead，比x大的頭插到bighead，最終得到如下兩個鏈表，
- 這里需要注意，由于開辟的鏈表的頭結點是哨兵結點，不儲存資料，兩個鏈表鏈接時，應該是大鏈表的哨兵位頭結點的后一個結點與小鏈表尾結點鏈接，大鏈表尾結點再置空，這樣就得到了分隔后的鏈表，
smalltail->next=bigHead->next;
bigtail->next=NULL;
? 
完整代碼
typedef struct ListNode Node;
struct ListNode* partition(struct ListNode* head, int x){
Node *smallHead,*smalltail,*bigHead,*bigtail;
smallHead=smalltail=(Node*)malloc(sizeof(Node));
bigHead=bigtail=(Node*)malloc(sizeof(Node));
smallHead->next=smalltail->next=NULL;
bigHead->next=bigtail->next=NULL;
while(head)
{
if(head->val<x)
{
smalltail->next=head;
smalltail=smalltail->next;
}
else
{
bigtail->next=head;
bigtail=bigtail->next;
}
head=head->next;
}
smalltail->next=bigHead->next;
bigtail->next=NULL;
return smallHead->next;
}
回文鏈表
題目鏈接點這里
思路：
-
判斷鏈表是否為回文鏈表，我們可以從中間結點處斷開，再逐一對比每個結點，而如何找到中間結點，依然可以用快慢指標的方法，慢指標每走一步，快指標就走兩步，當快指標走到尾時，慢指標指向的就是中間結點，但我們不是要在中間結點后斷開，而是要在中間結點的前一個結點斷開，那么我們還需要一個指標來保留慢指標的前一個結點，
-
但由于鏈表不能逆向遍歷，因此還要對第二個鏈表進行反轉，反轉的方法和上面鏈表反轉題目的第二種方法一樣，這里就不贅述了，
完整代碼
typedef struct ListNode Node;
bool isPalindrome(struct ListNode* head){
Node *fast = head;
Node *slow = head;
Node *prev = NULL;
if(head->next == NULL)
return true;
while(fast && fast->next)
{
prev = slow; // 保留slow的前一個結點
slow = slow->next; //快指標走兩步
fast = fast->next->next; //快指標走兩步
}
prev->next = NULL;//從prev結點后斷開
//鏈表反轉
Node *newhead = NULL;
Node *cur = slow;
while(cur)
{
Node *next =cur->next;
cur->next = newhead;
newhead = cur;
cur = next;
}
//兩個鏈表進行比較
while(head)
{
if(head->val == newhead->val)
{
head = head->next;
newhead = newhead->next;
}
else
return false;
}
return true;
}
e *newhead = NULL;
Node *cur = slow;
while(cur)
{
Node *next =cur->next;
cur->next = newhead;
newhead = cur;
cur = next;
}
//兩個鏈表進行比較
while(head)
{
if(head->val == newhead->val)
{
head = head->next;
newhead = newhead->next;
}
else
return false;
}
return true;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/398687.html
標籤：其他