持續更新
- 連結清單基礎知識
- 8道經典連結清單常考題目-----LeetCode
-
- 連結清單逆序（easy）-----206
- 連結清單逆序2（medium）-----92
- 連結清單求交點（easy）
- 連結清單求環（medium）
- 連結清單劃分（medium）
- 複雜連結清單的複制（hard）
- 2個排序連結清單歸并（easy）
- k個排序連結清單歸并（hard）
- 解題方法，代碼實作
- 一些學習與找工作建議
連結清單基礎知識
圖示：
代碼：
#include <stdio.h>
struct ListNode {
int val; //存儲元素的資料域
ListNode *next;
}; //存儲下一節點位址的指針域
int main(){
ListNode a;
ListNode b;
ListNode c;
ListNode d;
ListNode e;
a.val = 10;
b.val = 20;
c.val = 30;
d.val = 40;
e.val = 50;
a.next = &b; //------1-----
b.next = &c;
c.next = &d;
d.next = &e;
e.next=NULL; //----2-------
ListNode $head = &a;
while(head){
printf("%d\n",heas->val)
head = head->next; //-----3------
}
return 0;
}
8道經典連結清單常考題目-----LeetCode
連結清單逆序（easy）-----206
已知連結清單頭節點指針head，将連結清單逆序。（不可申請額外空間）
圖示：
在這裡插入圖檔描述
代碼：
struct ListNode {
int val; //存儲元素的資料域
ListNode *next;//指針域
ListNode(int x) : val(x), next(NULL) {}
}; //構造函數
class Solution{
public: //連結清單頭節點指針
ListNode* reverseList(ListNode* head){
} //傳回連結清單逆序後的頭節點指針
};
思路：
代碼：
class Solution{
public: //連結清單頭節點指針
ListNode* reverseList(ListNode* head){
ListNode *new_head = NULL;//指向新連結清單頭節點的指針
while(head){
ListNode *next = head->next;//備份head->next-----1-----
head->next = new_head;//更新head=>next-----2-----
new_head = head;//移動new_head----3-----
head = next;//周遊連結清單
}
return new_head;//傳回新連結清單頭節點
} //傳回連結清單逆序後的頭節點指針
};
測試：
int main(){
ListNode a;
ListNode b;
ListNode c;
ListNode d;
ListNode e;
a.next = &b;
b.next = &c;//将節點簡單的連結，進行測試
c.next = &d;//無需構造複雜的操作（插入，删除）
d.next = &e;
Solution solve;
ListNode *head = &a;
printf("Before reverse:\n");
while(head){
printf("%d\n",head->val);
head = head->next;
}
head = solve.reverseList(&a);
prtinf("After reverse:\n");
while(head){
printf("%d\n",head->val);
head = head->next;
}
return 0;
}
連結清單逆序2（medium）-----92
已知連結清單頭節點指針head，将連結清單從位置m到n逆序。（不申請額外空間）
圖示：
代碼：
class Solution{
public:
ListNode* reverseBetween(ListNode* head, int m, int n){
}
};
思路：
思考：
1.最終結果應該傳回哪個節點？
2.如果m=1時，有什麼特殊的？
代碼：
class Solution{
public:
ListNode* reverseBetween(ListNode* head,int m,int n){
int change_len =n - m + 1;//計算需要逆置的節點個數
ListNode *pre_head = NULL;//初始化開始逆置的節點的前驅
ListNode *result = head;//最終轉換後的連結清單頭節點，非特殊情況即為head
while(head && ==m){ //将head向前移動m-1個位置
//-------1-------
head = head->next;
} //将modify_list_tail指向目前的head，即逆置後的連結清單尾
ListNode *modify_list_tail = head;
ListNode *new_heaad = NULL;
while(head && change_len){//逆置change——len個節點
ListNode *next = head->next;
head->next = new_head;
new_head = head;
head = next;
//-------2-----
}
//-----3------
if (pre_head){ //如果pro——head不變，說明不是從第一個結點開始逆置的m》1
//-----4------
}
else{
//--------5-----
}
return result;
}
};