目錄
前言
1.移除鏈表元素
2.反轉鏈表
3.鏈表的中間結點
4.鏈表中的倒數第K個結點
5.合并兩個有序鏈表
6.分割鏈表
7.回文鏈表
8.相交鏈表
9.環形鏈表
10.環形鏈表II
11.復制帶隨機指標的鏈表
前言
前面我們學習了鏈表，并實作了單鏈表，關于鏈表的OJ題在面試時也經常考到，學會了這些OJ題，鏈表對于你來說就是小菜一碟了，
1.移除鏈表元素
移除鏈表元素
這道題比較簡單，依次遍歷鏈表，如果該結點的值等于需要洗掉的值，直接洗掉掉該結點即可，
但需注意其中的特殊情況：
- 鏈表為空，
- 頭結點為需要洗掉結點，
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val){
//考慮鏈表為空的情況
if(head == NULL)
{
return NULL;
}
//鏈表不為空
ListNode*cur = head;//用來遍歷鏈表(一般不使用head遍歷，這樣會找不到頭結點)
ListNode*prev = NULL;//用來保存需要洗掉結點的前一個結點
while(cur)
{
if(cur->val == val)
{
//頭結點為需要洗掉的結點
if(cur == head)
{
head = head->next;//將頭結點右移
free(cur);
cur = head;
}
else
{
ListNode*next = cur->next;//保存下一個結點
prev->next = next;//將需要洗掉結點的前一個結點指向下一個結點
free(cur);
cur = next;
//這里也可以不創建next變數
//prev->next = cur->next;
//free(cur);
//cur = prev->next;
}
}
else
{
prev = cur;//保存上一個節點
cur = cur->next;//向右移動
}
}
return head;
}2.反轉鏈表
反轉鏈表
這里有兩種方法：
1.三指標法：即創建三個指標n1,n2,n3，n1,n2用來反轉兩個結點，n3用來保存下一個結點的地址，反轉后依次迭代直到n2為NULL，如圖：
代碼如下：
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head){
//因為后面head需要解參考所以必須要考慮鏈表為NULL的情況
if(head==NULL)
{
return NULL;
}
ListNode*n1 = NULL;
ListNode*n2 = head;
ListNode*n3 = head->next;
while(n2)
{
n2->next = n1;
n1 = n2;
n2 = n3;
//因為是以n2為NULL為回圈結束條件，需保證n3不為NULL時，再迭代n3
if(n3!=NULL)
{
n3 = n3->next;
}
}
return n1;
}2.頭插法：即建立新的頭結點，將原鏈表每個結點取下來頭插到新頭結點上，然后將新頭結點左移，如圖：
代碼如下：
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head){
ListNode*newhead = NULL;//這里不需要判斷鏈表為NULL的情況，鏈表為NULL也能處理
ListNode*cur = head;
while(cur)
{
ListNode*next = cur->next;
cur->next = newhead;
newhead = cur;
cur = next;
}
return newhead;
}注：起始兩種方法的代碼非常類似，但思路卻不相同，
3.鏈表的中間結點
鏈表的中間結點
方法：快慢指標
即慢指標一次走一步，快指標一次走兩步，快指標走到NULL時慢指標會剛好到鏈表的中間結點，
如圖：
代碼如下：
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head){
ListNode*fast = head;
ListNode*slow = head;
while(fast&&fast->next)//回圈結束條件為fast為NULL或fast->next為NULL
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}4.鏈表中的倒數第K個結點
鏈表中的倒數第K個結點
方法：快慢指標
快指標先走K步，然后快慢指標同時走，直到快指標為NULL，
(注：這里的快指標一次走一步)
如圖：
代碼如下：
typedef struct ListNode ListNode;
struct ListNode* getKthFromEnd(struct ListNode* head, int k){
ListNode*fast = head;
ListNode*slow = head;
while(k--)//fast先走
{
if(fast==NULL)//當K大于等于結點個數時，fast會走到NULL
{
return NULL;
}
fast = fast->next;
}
while(fast)//fast，slow同時走
{
fast = fast->next;
slow = slow->next;
}
return slow;
}5.合并兩個有序鏈表
和并兩個有序鏈表
方法：創建頭結點，依次比較兩個鏈表每個結點的大小，將較小的結點尾插到頭結點的后面，
注意：
- 使用哨兵位的頭結點會比較簡單，
- l1或l2中一個為NULL的情況，
- 當兩個鏈表不相等時，不要忘記將剩余結點連接到合并鏈表的后面，
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
//l1為NULL
if (l1 == NULL)
{
return l2;
}
//l2為NULL
if (l2 == NULL)
{
return l1;
}
//都不為NULL
ListNode*head = NULL;
ListNode*tail = NULL;
head = tail =(ListNode*)malloc(sizeof(ListNode));//創建哨兵位頭結點，即頭結
//點不存放有效值.
while(l1&&l2)
{
if(l1->val<l2->val)
{
tail->next = l1;
l1 = l1->next;
}
else
{
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
//結點剩余情況
if(l1==NULL)
{
tail->next = l2;
}
else
{
tail->next = l1;
}
//釋放哨兵位頭結點
tail = head;
head = head->next;
free(tail);
tail = NULL;
return head;
}哨兵位頭結點：不保存有效值，
優點：連接結點時不需判斷頭結點是否為NULL，直接連接在頭結點后面即可，
注意：回傳時需回傳頭結點的下一個結點，且需釋放哨兵位結點，
6.分割鏈表
分割鏈表
方法：創建兩個頭結點head1，head2，將小于x的結點尾插到head1后面；將大于等于x的結點尾插到head2的后面，（注意：不要改變原結點的順序）
如圖：
代碼如下：
typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x){
ListNode*head1 = (ListNode*)malloc(sizeof(ListNode));//創建兩個哨兵位頭結點
ListNode*head2 = (ListNode*)malloc(sizeof(ListNode));
head1->next = NULL;
head2->next = NULL;
ListNode*cur = head;//用來遍歷原鏈表
ListNode*tail1 = head1;//用來保存head1尾結點
ListNode*tail2 = head2;//用來保存head2尾結點
while(cur)
{
if(cur->val<x)//小于x尾插到head1鏈表
{
tail1->next = cur;
tail1 = tail1->next;
}
else//大于等于x尾插到head2鏈表
{
tail2->next = cur;
tail2 = tail2->next;
}
cur = cur->next;
}
tail2->next = NULL;//將head2鏈表的尾結點指向NULL，可能head2的尾結點還指向原鏈表中的結點，導致連接后鏈表成環，
tail1->next = head2->next;//連接head1，head2鏈表
ListNode*newhead = head1->next;//保存有效頭結點
free(head1);//釋放哨兵位頭結點
free(head2);
head1 = NULL;
head2 = NULL;
return newhead;
}注意：若未將head2的尾結點的next指向NULL，則會出現一下情況：
7.回文鏈表
回文鏈表
方法：找到鏈表的中間結點，將鏈表一分為二，將前后任意部分反轉，依次必將兩部分鏈表每個結點是否相等，
注：
- 鏈表結點為NULL或結點個數為0時回傳true，
- 鏈表結點個數為奇數個時，中間結點不會影響結果，
如圖：
typedef struct ListNode ListNode;
bool isPalindrome(struct ListNode* head){
//鏈表為慷訓鏈表只有一個結點的情況
if(head==NULL||head->next==NULL)
{
return true;
}
//找中間結點
ListNode*fast = head;
ListNode*slow = head;
ListNode*prev = NULL;//保存前一個結點
while(fast && fast->next)
{
prev = slow;
fast = fast->next->next;
slow = slow->next;
}
//斷開兩鏈表
prev->next = NULL;
//反轉后面鏈表
ListNode*newhead = NULL;
while(slow)
{
ListNode*next =slow->next;
slow->next = newhead;
newhead = slow;
slow = next;
}
//比較兩鏈表每個結點
while(head && newhead)//當鏈表結點個數為奇數時，兩鏈表的長度不相等，所以只要有一個鏈表為空就結束回圈
{
if(head->val != newhead->val)
{
return false;
}
head = head->next;
newhead = newhead->next;
}
return true;
}8.相交鏈表
相交鏈表
方法1(暴力求解)：依次將A鏈表中的每個結點與B鏈表的每個結點相比，直到A鏈表為NULL，
(時間復雜度：O(N^2))
代碼如下：
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
ListNode* curA = headA;
ListNode* curB = headB;
while(curA)
{
while(curB)
{
if(curA == curB)
{
return curA;
}
curB = curB->next;
}
curA = curA->next;
curB = headB;
}
return NULL;
}方法2：
- 可先比較兩鏈表的最后一個結點是否相等，若相等則兩鏈表必相交，否則不相交，
- 如果相交則先分別計算出A，B鏈表的長度，算出長度差，
- 將較長鏈表先走差距步，然后兩鏈表再同時走，
- 判斷依次判斷結點是否相等，
代碼如下：
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
ListNode* curA = headA;
ListNode* curB = headB;
int lenA = 1;
int lenB = 1;
//找到兩鏈表的尾結點，順便計算出兩鏈表的長度
while(curA->next)
{
curA = curA->next;
lenA++;
}
while(curB->next)
{
curB = curB->next;
lenB++;
}
//如果兩鏈表尾結點不相等則兩鏈表不相交
if(curA!=curB)
{
return NULL;
}
//計算兩鏈表長度差
int gap = abs(lenA-lenB);
//長鏈表先走差距步
if(lenA>lenB)
{
while(gap--)
{
headA = headA->next;
}
}
else
{
while(gap--)
{
headB = headB->next;
}
}
//依次比較兩鏈表的每個結點
while(headA!=headB)
{
headA = headA->next;
headB = headB->next;
}
return headA;
}9.環形鏈表
環形鏈表
方法：快慢指標
快指標一次走兩步，慢指標一次走一步，如果鏈表無環，則快指標會走到NULL；如果鏈表有環，快指標會先入環，慢指標后入環，在環內快指標會追上慢指標，
如圖：
代碼如下：
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {
ListNode* slow = head;
ListNode* fast = head;
while(fast&&fast->next)
{
slow = slow->next;
fast = fast->next->next;
//鏈表有環，則回圈不會結束，直到slow=fast回傳true
if(slow == fast)
{
return true;
}
}
//鏈表無環，回圈結束回傳false
return false;
}10.環形鏈表II
環形鏈表II(回傳鏈表入環點)
方法：快慢指標+公式運算
- 根據快慢指標判斷鏈表是否有環，
- 如果有環，根據快指標走的路程等于慢指標走的路程的2倍，
如圖：
代碼如下：
typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {
ListNode*fast = head;
ListNode*slow = head;
//判斷鏈表是否有環
while(fast&&fast->next)
{
fast = fast->next->next;
slow = slow->next;
//鏈表有環
if(slow==fast)
{
//根據等式尋找入環點
ListNode*cur = head;
while(cur!=fast)
{
cur = cur->next;
fast = fast->next;
}
return cur;
}
}
return NULL;
}面試官反問：
為什么fast和slow一定會在環中相遇？會不會錯過？
為什么快指標一次要走兩部，而不是走三步，四步......?
如圖：
11.復制帶隨機指標的鏈表
復制帶隨機指標的鏈表
這個題的長度看著就有些勸退啊，但我們只要直到方法其實并不難，
可能有些人會覺得，誒不是直接將鏈表的每個結點拷貝一下就行了嗎？
雖然我們直到拷貝之前的random，但拷貝之后的random的具體位置與拷貝之前是沒有任何關系的，所以不能使用這種方法，
如何去復制一個帶隨機指標的鏈表？
首先我們可以忽略 random 指標，然后對原鏈表的每個節點進行復制，并追加到原節點的后面，而后復制 random 指標，最后我們把原鏈表和復制鏈表拆分出來，并將原鏈表復原，
圖示程序如下：
1、在每個節點的后面加上它的復制，并將原鏈表和復制鏈表連在一起，
2、 從前往后遍歷每一個原鏈表節點，對于有 random 指標的節點 p，我們讓它的 p->next->random = p->random->next，這樣我們就完成了對原鏈表 random 指標的復刻，
3、最后我們把原鏈表和復制鏈表拆分出來，并將原鏈表復原，
具體程序如下：
- 定義一個 cur 指標，遍歷整個鏈表，復制每個節點，并將原鏈表和復制鏈表連在一起，
- 再次遍歷整個鏈表，執行 newnode->random = cur->random->next，復制 random 指標，
- 定義newhead 用來指向復制鏈表的頭節點， 將兩個鏈表拆分并復原原鏈表，
時間復雜度分析： O(n)O(n)，其中 n 是鏈表的長度，
代碼如下：
typedef struct Node Node;
struct Node* copyRandomList(struct Node* head) {
//拷貝結點到原結點的后面
Node*cur = head;
while(cur)
{
Node*newnode = (Node*)malloc(sizeof(Node));
Node*next = cur->next;
cur->next = newnode;
newnode->val = cur->val;
newnode->next = next;
cur = next;
}
//將拷貝結點的random連接到上一個結點的next
cur = head;
while(cur)
{
Node*copy = cur->next;
Node*next = copy->next;
if(cur->random == NULL)
{
copy->random = NULL;
}
else
{
copy->random =cur->random->next;
}
cur = next;
}
//斷開拷貝結點，恢復原鏈表
cur = head;
Node*newhead = (Node*)malloc(sizeof(Node));
newhead->next= NULL;
//newhead = head->next;
Node*tail = newhead;
while(cur)
{
Node*copy = cur->next;
Node*next = copy->next;
tail->next = copy;
tail = copy;
cur->next = next;
cur = next;
}
Node*copyhead = newhead->next;
free(newhead);
newhead = NULL;
return copyhead;
}這些你學到了嗎？
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/340753.html
標籤：其他