1. 移除鏈表元素
思路1：遍歷原鏈表，將 val 所在的節(jié)點釋放掉。(太麻煩)
思路2：創(chuàng)建新鏈表，再遍歷原鏈表，找到不為 val 的節(jié)點尾插到新鏈表。
思路1代碼實現(xiàn)如下：
注意：
1.當(dāng)鏈表為空時，直接返回NULL即可。
2.當(dāng)尾插上最后一個有效節(jié)點時，此時它的 next 可能還與最后一個節(jié)點相鏈接，一定要斷開！
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
if (head == NULL)
return NULL;
//創(chuàng)建一個新鏈表
ListNode* newHead, * newTail;
newHead = newTail = NULL;
ListNode* pcur = head;
//遍歷原鏈表，找不為val的節(jié)點尾插
while (pcur)
{
ListNode* next = pcur->next;
if (pcur->val != val)
{
//沒有一個節(jié)點
if (newHead == NULL)
{
newHead = newTail = pcur;
}
else
{
//有一個節(jié)點以上
newTail->next = pcur;
newTail = newTail->next;
}
}
pcur = next;
}
if (newTail)
newTail->next = NULL;
return newHead;
}
2. 反轉(zhuǎn)鏈表
2.1反轉(zhuǎn)指針法
思路：定義三個變量 n1，n2，n3，根據(jù)它們的指向關(guān)系進(jìn)行迭代。
代碼實現(xiàn)如下：文章來源：http://www.zghlxwxcb.cn/news/detail-851101.html
注意：
1.當(dāng)鏈表為空時，直接返回NULL即可。
2.在迭代過程中別忘記判斷 n3 ，防止對空指針解引用。
3.注意循環(huán)結(jié)束的條件，當(dāng) n2 為空時，n1 指向反轉(zhuǎn)后的頭，此時循環(huán)結(jié)束。
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
if (head == NULL)
return NULL;
ListNode* n1, * n2, * n3;
n1 = NULL, n2 = head, n3 = n2->next;
while (n2)
{
n2->next = n1;
n1 = n2;
n2 = n3;
if (n3)
n3 = n3->next;
}
return n1;
}
2.2 頭插法
思路：創(chuàng)建一個新鏈表，遍歷原鏈表，依次取下原鏈表的每一個節(jié)點頭插到新鏈表中。
代碼實現(xiàn)如下：
注意：
1.當(dāng)鏈表為空時，直接返回NULL即可。
2.頭插時可以不用判斷沒有節(jié)點和有節(jié)點的情況。
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
if (head == NULL)
return NULL;
ListNode* newHead, * newTail;
newHead = newTail = NULL;
ListNode* pcur = head;
//一個一個拿下來頭插
while (pcur)
{
ListNode* next = pcur->next;
pcur->next = newHead;
newHead = pcur;
pcur = next;
}
return newHead;
}
3. 合并兩個有序鏈表
思路：創(chuàng)建一個帶哨兵位的新鏈表，遍歷兩個原鏈表，比較兩個節(jié)點的值，哪個小就先尾插到新鏈表中。
代碼實現(xiàn)如下：
注意：
1.當(dāng)其中一個鏈表為空時，返回另一個鏈表即可。
2.創(chuàng)建哨兵位節(jié)點，方便尾插。
3.注意循環(huán)結(jié)束條件，當(dāng)其中有一個鏈表走完時，跳出循環(huán)。
4.剩下的沒走完的那個鏈表直接鏈接到后面。不需要用循環(huán)鏈接，因為它們本來就是連在一起的。
5.別忘記釋放釋放哨兵位節(jié)點，釋放前要保存下一個節(jié)點。
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
ListNode* n1, * n2;
n1 = list1;
n2 = list2;
if (n1 == NULL)
return n2;
if (n2 == NULL)
return n1;
//創(chuàng)建哨兵位節(jié)點
ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
ListNode* newHead, * newTail;
newHead = newTail = phead;
while (n1 && n2)
{
//比較兩個鏈表中數(shù)據(jù)的大小，誰小就先尾插到新鏈表
if (n1->val < n2->val)
{
newTail->next = n1;
n1 = n1->next;
newTail = newTail->next;
}
else
{
newTail->next = n2;
n2 = n2->next;
newTail = newTail->next;
}
}
if (n1)
newTail->next = n1;
if (n2)
newTail->next = n2;
ListNode* ret = newHead->next;
free(newHead);
return ret;
}
4. 分隔鏈表
思路：創(chuàng)建兩個帶哨兵位的新鏈表 less 和 greater 。遍歷原鏈表，把小于x 的節(jié)點尾插到 less 鏈表中，把大于等于x 的節(jié)點尾插到greater 鏈表中。最后把 less 鏈表中的尾結(jié)點的 next 鏈接到 greater鏈表中的頭結(jié)點上。
代碼實現(xiàn)如下：
注意：
1.當(dāng)鏈表尾空時，直接返回NULL即可。
2.有可能存在greater 鏈表中的最后一個結(jié)點與原鏈表中的最后一個結(jié)點仍然相鏈接的情況，一定要斷開！
typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x) {
if (head == NULL)
return NULL;
ListNode* lessHead, * lessTail, * greaterHead, * greaterTail;
ListNode* pcur = head;
//創(chuàng)建哨兵位節(jié)點，方便尾插
lessHead = lessTail = (ListNode*)malloc(sizeof(ListNode));
greaterHead = greaterTail = (ListNode*)malloc(sizeof(ListNode));
lessTail->next = NULL;
greaterTail->next = NULL;
while (pcur)
{
if (pcur->val < x)
{
lessTail->next = pcur;
lessTail = lessTail->next;
}
else
{
greaterTail->next = pcur;
greaterTail = greaterTail->next;
}
pcur = pcur->next;
}
lessTail->next = greaterHead->next;
greaterTail->next = NULL;
return lessHead->next;
}
5. 環(huán)形鏈表
這是一個非常經(jīng)典的例題，它要用上一種非常經(jīng)典的算法：快慢指針法。
定義一個 slow 變量，fast 變量，從鏈表的頭結(jié)點開始，slow 每次走一步，fast 每次走兩步，當(dāng) slow 進(jìn)入環(huán)中時，fast 開始追逐。若成環(huán)，則必會在環(huán)內(nèi)的某處相遇，否則 fast 或是 fast->next 最后會走到NULL。
代碼實現(xiàn)如下：
注意：
1.當(dāng)鏈表節(jié)點個數(shù)為偶數(shù)個時，若不成環(huán)，最終 fast == NULL。
當(dāng)鏈表節(jié)點個數(shù)為奇數(shù)個時，若不成環(huán)，最終 fast->next == NULL.
2.循環(huán)條件 fast && fast->next 的位置不能交換。因為當(dāng)為偶數(shù)個節(jié)點，fast走到NULL時，如果是 fast->next && fast ，那就是先執(zhí)行 fast->next ，對空指針解引用，錯誤??！
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode* head) {
ListNode* slow, * fast;
slow = fast = head;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if (fast == slow)
return true;
}
return false;
}
6. 鏈表的中間節(jié)點
也要用快慢指針法。也要分兩種情況：
代碼實現(xiàn)如下：
注意：
循環(huán)條件 fast && fast->next 的位置不能交換。因為當(dāng)為偶數(shù)個節(jié)點，fast走到NULL時，如果是 fast->next && fast ，那就是先執(zhí)行 fast->next ，對空指針解引用，錯誤?。?/strong>
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
7. 鏈表中倒數(shù)第K個節(jié)點
思路：
(1) fast 先走 k 步；
(2) slow 和 fast 再一起走，當(dāng) fast == NULL 時，slow 就是倒數(shù)第 k 個節(jié)點。
代碼實現(xiàn)如下：
注意：
當(dāng) k 大于鏈表長度時，fast 會走到 NULL ，不能對空指針解引用，直接返回 NULL。
typedef struct ListNode ListNode;
struct ListNode* FindKthToTail(struct ListNode* pHead, int k ) {
ListNode* fast ,*slow;
fast = slow = pHead;
//fast先走K步
while(k--)
{
//K大于鏈表長度時，直接返回NULL
if(fast == NULL)
{
return NULL;
}
fast = fast->next;
}
//再兩者一起走
while(fast)
{
fast = fast->next;
slow = slow->next;
}
return slow;
}
8. 相交鏈表
首先要明確什么是相交鏈表：
思路1：暴力求解，時間復(fù)雜度O(N*N)
依次取A鏈表中的每個節(jié)點跟B鏈表中的所有節(jié)點比較。如果有相同地址的節(jié)點，則相交，第一次相同地址的節(jié)點就是交點，否則就不相交。
思路2：時間復(fù)雜度O(N)
(1) 先找到兩個鏈表的尾,同時計算出兩個鏈表的長度；
(2) 求出長度差；
(3) 判斷哪個是長鏈表；
(4) 讓長鏈表先走長度差步；
(5) 最后長短鏈表一起走，直到找到交點。
思路2代碼實現(xiàn)如下：
注意：
要注意步驟(3)中判斷長短鏈表的巧妙方法?？梢员苊鈱懼貜?fù)代碼。
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
ListNode* TailA,*TailB;
TailA = headA;
TailB = headB;
//找尾同時計算長度
int lenA = 0;
int lenB = 0;
while(TailA->next)
{
TailA = TailA->next;
lenA++;
}
while(TailB->next)
{
TailB = TailB->next;
lenB++;
}
//不相交
if(TailA != TailB)
{
return NULL;
}
//求出長度差
int gap = abs(lenA - lenB);
//判斷哪個是長鏈表
ListNode* longList = headA;//先默認(rèn)A是長鏈表
ListNode* shortList = headB;
if(lenA < lenB)
{
shortList = headA;
longList = headB;
}
//讓長鏈表走長度差步
while(gap--)
{
longList = longList->next;
}
//最后長短鏈表一起走，找交點
while(longList != shortList)
{
longList = longList->next;
shortList = shortList->next;
}
return longList;
}
9. 環(huán)形鏈表的約瑟夫問題
思路：
首先要創(chuàng)建一個循環(huán)鏈表，定義一個計數(shù)器 count 用于數(shù)數(shù)，再遍歷循環(huán)鏈表，當(dāng)結(jié)點的 val == count 時，就"殺死"，即銷毀該節(jié)點。
代碼實現(xiàn)如下：
注意：
要學(xué)習(xí)創(chuàng)建循環(huán)鏈表的方法！
typedef struct ListNode ListNode;
//創(chuàng)建節(jié)點
ListNode* BuyNode(int x)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
if(newnode == NULL)
{
exit(-1);
}
newnode->val = x;
newnode->next = NULL;
return newnode;
}
//1.創(chuàng)建循環(huán)鏈表
ListNode* Createnodecircle(int n)
{
ListNode* phead = BuyNode(1);
ListNode* ptail = phead;
for(int i=2;i<=n;i++)
{
ptail->next = BuyNode(i);
ptail = ptail->next;
}
//尾連頭，成環(huán)
ptail->next = phead;
return ptail;
}
int ysf(int n, int m ) {
ListNode* prev = Createnodecircle(n);
ListNode* pcur = prev->next;
//開始數(shù)數(shù)
int count = 1;
while(pcur->next!=prev->next)
{
if(count == m)
{
prev->next = pcur->next;
free(pcur);
pcur = prev->next;
count = 1;
}
else
{
prev = pcur;
pcur = pcur->next;
count++;
}
}
return pcur->val;
}
10. 鏈表的回文結(jié)構(gòu)
這個題在?？途W(wǎng)中不能用C語言實現(xiàn)，我們可以選C++，因為C++是兼容C的，在C++中可以使用C的語法。
思路：
(1) 找到鏈表的中間節(jié)點；
(2) 把中間節(jié)點后面的鏈表進(jìn)行逆置；
(3) 最后把逆置后的鏈表的值與中間節(jié)點之前的鏈表的值進(jìn)行比較，若所有節(jié)點相等，則是回文鏈表，否則不是。有一個鏈表結(jié)束則比較結(jié)束。
代碼實現(xiàn)如下：
注意：
逆置完之后，中間節(jié)點與前一個結(jié)點的鏈接可以不用斷開，因為就算鏈接在一起也不影響判斷。若強行斷開，徒增麻煩。文章來源地址http://www.zghlxwxcb.cn/news/detail-851101.html
//找中間結(jié)點
struct ListNode* middleNode(struct ListNode* head) {
struct ListNode* slow = head;
struct ListNode* fast = head;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
//對中間結(jié)點之后的鏈表進(jìn)行逆置
struct ListNode* reverseList(struct ListNode* head) {
if (head == NULL)
return NULL;
struct ListNode* n1, * n2, * n3;
n1 = NULL, n2 = head, n3 = n2->next;
while (n2)
{
n2->next = n1;
n1 = n2;
n2 = n3;
if (n3)
n3 = n3->next;
}
return n1;
}
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
struct ListNode* mid = middleNode(A);
struct ListNode* rHead = reverseList(mid);
struct ListNode* curA = A;
struct ListNode* curR = rHead;
//把逆置后的鏈表與中間結(jié)點之前的鏈表進(jìn)行比較
while(curA && curR)
{
if(curA->val != curR->val)
{
return false;
}
else
{
curA = curA->next;
curR = curR->next;
}
}
return true;
}
};
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)與算法】：10道鏈表經(jīng)典OJ的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
