文章目錄
- 一. 移除鏈表元素
- 二. 鏈表的中間結點
- 三. 鏈表中倒數第k個結點
- 四. 合并兩個有序鏈表
- 五. 分割鏈表
- 六. 反轉鏈表
- 七. 鏈表的回文結構
- 八.相交鏈表
- 九.環形鏈表
一. 移除鏈表元素
原題鏈接:
移除鏈表元素
第一種方法: 直接洗掉法
這種方法需要特殊考慮頭結點的洗掉情況
首先考慮一般情況 ,洗掉的不是頭結點，定義兩個指標 prev , cur 一前一后，逐步洗掉移動
我們由圖中可以看到，如果洗掉的是頭結點，prev->next = cur->next 該步就會出錯，因為 prev 此時是空指標
洗掉頭結點的情況如下:
給出代碼 :
struct ListNode* removeElements(struct ListNode* head, int val)
{
if(head == NULL)
{
return NULL;
}
struct ListNode* prev = NULL,* cur = head;
while(cur != NULL)
{
if(cur->val == val)
{
// 洗掉頭結點的情況
if(cur == head)
{
cur = cur->next;
free(head);
head = cur;
}
// 洗掉非頭結點的情況
else
{
prev->next = cur->next;
free(cur);
cur = prev->next;
}
}
else
{
prev = cur;
cur = cur->next;
}
}
return head;
}
第二種方法 : 創建虛擬頭結點
該方法可以將洗掉頭結點和其他結點的情況進行統一
我們創建一個新節點來作為整個鏈表的頭結點，該節點中的值沒有意義，只是用該節點來方便我們的操作，如果用DummyNode->next=head; 此時 我們操作DummyNode的話就把第一個結點當做了一個普通節點來操作，此時頭結點就可以被洗掉了，最后回傳DummyNode->next就滿足條件了，正是由于有個無意義節點作為頭結點會統一操作（把頭結點當做普通節點）所以實際鏈表設計程序中都是有個無意義頭結點的，遇到第一個結點不好解決的問題，大家可以設一個節點試試，
給出代碼 :
typedef struct ListNode ListNode;
// 創建虛擬頭結點
ListNode* CreateListNode()
{
ListNode* DummyNode = (ListNode*)malloc(sizeof(ListNode));
if(DummyNode == NULL)
{
exit(-1);
}
else
{
DummyNode->next = NULL;
}
return DummyNode;
}
struct ListNode* removeElements(struct ListNode* head, int val)
{
ListNode* DummyNode = CreateListNode();
ListNode* cur = head,* prev = DummyNode;
DummyNode->next = head;
head = DummyNode;
// 執行洗掉操作
while(cur != NULL)
{
if(cur->val == val)
{
prev->next = cur->next;
free(cur);
cur = prev->next;
}
else
{
prev = cur;
cur = cur->next;
}
}
return head->next;
}
方法三 : 遞回
遞回思路:
給出代碼 :
struct ListNode* removeElements(struct ListNode* head, int val)
{
if(head == NULL)
{
return NULL;
}
head->next = removeElements(head->next,val);
return (head->val == val) ? head->next : head;
}
二. 鏈表的中間結點
原題鏈接 :
鏈表的中間結點
第一種方法 :
快慢指標
(1) 鏈表結點個數為奇數個時 :
(2) 鏈表結點個數為偶數個時 :
給出代碼 :
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* fast = head,* slow = head;
while(fast != NULL && fast->next != NULL)
{
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
三. 鏈表中倒數第k個結點
原題鏈接 :
鏈表中倒數第k個結點
方法: 快慢指標
先讓快指標走 k 步，接著快指標和慢指標一起走，當快指標走到 NULL 時，慢指標走到倒數第 k 個結點
注意判斷一下 k 是否超出鏈表的長度
給出代碼 :
struct ListNode* getKthFromEnd(struct ListNode* head, int k)
{
if(head == NULL)
{
return NULL;
}
struct ListNode* fast = head,* slow = head;
// fast指標先走 k 步
while(k--)
{
// 判斷 k 是否滿足條件
if(fast != NULL)
{
fast = fast->next;
}
else
{
return NULL;
}
}
// 快慢指標同時移動
while(fast != NULL)
{
fast = fast->next;
slow = slow->next;
}
return slow;
}
四. 合并兩個有序鏈表
原題鏈接 :
合并兩個有序鏈表
第一種方法 : 尾插迭代法
給出代碼 :
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{
if(l1 == NULL || l2 == NULL)
{
return (l1 == NULL) ? l2 : l1;
}
ListNode* head = NULL,* tail = NULL;
head = tail = (ListNode*)malloc(sizeof(ListNode));
while(l1 != NULL && l2 != NULL)
{
if(l1->val <= l2->val)
{
tail->next = l1;
tail = tail->next;
l1 = l1->next;
}
else
{
tail->next = l2;
tail = tail->next;
l2 = l2->next;
}
}
if(l1 == NULL)
{
tail->next = l2;
}
else
{
tail->next = l1;
}
return head->next;
}
第二種方法 : 遞回
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
if(l1==NULL)
return l2;
if(l2==NULL)
return l1;
if(l1->val <= l2->val)
{
l1->next = mergeTwoLists(l1->next,l2);
return l1;
}else
{
l2->next = mergeTwoLists(l1,l2->next);
return l2;
}
}
五. 分割鏈表
原題鏈接 :
分割鏈表
給出代碼 :
class Partition {
public:
ListNode* partition(ListNode* pHead, int x)
{
ListNode* LessHead = (ListNode*)malloc(sizeof(ListNode));
ListNode* GreaterHead = (ListNode*)malloc(sizeof(ListNode));
LessHead->next = GreaterHead->next = NULL;
ListNode* LessHeadTail = LessHead;
ListNode* GreaterHeadTail = GreaterHead;
ListNode* cur = pHead;
while (cur != NULL)
{
if (cur->val < x)
{
LessHeadTail->next = cur;
LessHeadTail = LessHeadTail->next;
}
else
{
GreaterHeadTail->next = cur;
GreaterHeadTail = GreaterHeadTail->next;
}
cur = cur->next;
}
GreaterHeadTail->next = NULL;
LessHeadTail->next = GreaterHead->next;
ListNode* List = LessHead->next;
free(LessHead);
free(GreaterHead);
return List;
}
};
六. 反轉鏈表
原題鏈接 :
反轉鏈表
第一種方法 : 雙指標
給出代碼 :
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head)
{
ListNode* n1 = NULL;
ListNode* n2 = head;
while(n2 != NULL)
{
ListNode* n3 = n2->next;
n2->next = n1;
n1 = n2;
n2 = n3;
}
return n1;
}
第二種方法 : 頭插法
設定一個新節點 newNode , 采取單鏈表中講解到的頭插的方法 ，即可達到逆序鏈表的目的
給出代碼 :
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head)
{
// 設定新節點
ListNode* newNode = NULL,* cur = head;
// 進行頭插操作，因為每次改變了 cur->next , 所以用 next 保存 cur 的下一個結點
while(cur != NULL)
{
ListNode* next = cur->next;
cur->next = newNode;
newNode = cur;
cur = next;
}
return newNode;
}
七. 鏈表的回文結構
原題鏈接 :
鏈表的回文結構
方法 : 先找到鏈表的中間結點 ， 具體方法可參考第二題 ， 接著逆序從中間結點起往后的部分（逆序操作可看第六題），判斷逆序后和前半部分結點是否相等
給出代碼 :
typedef struct ListNode ListNode;
// 逆序鏈表操作
ListNode* reverseList(ListNode* head)
{
ListNode* n1 = NULL;
ListNode* n2 = head;
while(n2 != NULL)
{
ListNode* n3 = n2->next;
n2->next = n1;
n1 = n2;
n2 = n3;
}
return n1;
}
class PalindromeList {
public:
bool chkPalindrome(ListNode* A)
{
ListNode* fast = A;
ListNode* slow = A;
ListNode* prev = NULL;
// 找到鏈表中間結點
while(fast != NULL && fast->next != NULL)
{
prev = slow;
slow = slow->next;
fast = fast->next->next;
}
slow = reverseList(slow);
// 判斷前半部分結點和后半部分結點是否相等
while(A != NULL && slow != NULL)
{
if(A->val != slow->val)
{
return false;
}
else
{
A = A->next;
slow = slow->next;
}
}
return true;
}
};
八.相交鏈表
原題鏈接 :
相交鏈表
方法 :
（1）. 分別遍歷兩個鏈表，求出兩個鏈表的長度 la , lb
（2）.讓指向較長鏈表的指標移動 abs(lb - la)步
（3）.兩個指標同時移動，若存在兩個指標相等的情況，則回傳該結點，若不存在，則回傳NULL
給出代碼 :
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
if(headA == NULL || headB == NULL)
{
return NULL;
}
ListNode* curA = headA,* curB = headB;
int la = 0,lb = 0;
// 求鏈表 A 的長度
while(curA !=NULL)
{
la++;
curA = curA->next;
}
// 求鏈表 B 的長度
while(curB != NULL)
{
lb++;
curB = curB->next;
}
curA = headA,curB = headB;
int count = (lb > la) ? (lb - la) : (la - lb);
int i = 0;
// 讓指向較長鏈表的指標移動 abs(lb - la)步
for(i = 0;i < count;i++)
{
if(lb > la)
{
curB = curB->next;
}
else
{
curA = curA->next;
}
}
// 兩個指標同時移動
while(curA && curB)
{
if(curA != curB)
{
curA = curA->next;
curB = curB->next;
}
else
{
return curA;
}
}
return NULL;
}
九.環形鏈表
原題鏈接 :
環形鏈表
當一個鏈表有環時，快慢指標都會陷入環中進行無限次移動，然后變成了追及問題，想象一下在操場跑步的場景，只要一直跑下去，快的總會追上慢的，當兩個指標都進入環后，每輪移動使得慢指標到快指標的距離增加一，同時快指標到慢指標的距離也減少一，只要一直移動下去，快指標總會追上慢指標，
給出代碼 ：
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head)
{
if(head == NULL)
{
return false;
}
ListNode* fast = head,* slow = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(fast == slow)
{
return true;
}
}
return false;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/264203.html
標籤：其他