系列文章目錄
文章目錄
- 系列文章目錄
- 前言
- 一、鏈表的中間結點
- 1.題目描述
- 2.解題思路
- 二、鏈表的倒數第k個結點
- 1.題目描述
- 2.解題思路
- 三、合并兩個排序的鏈表
- 1.題目描述
- 2.解題思路
- 總結
前言
一、鏈表的中間結點
鏈表的中間結點
1.題目描述
給定一個頭結點為 head 的非空單鏈表，回傳鏈表的中間結點，如果有兩個中間結點，則回傳第二個中間結點，
2.解題思路
可以采用快慢指標方法:設定兩指標，慢指標速度一次一個結點，快指標一次兩個結點，這種方法只遍歷了一次鏈表
代碼如下：
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
struct ListNode
{
int val;
struct ListNode* next;
};
//快慢指標方法
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* fast = head, *slow = head;
while (fast&&fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
二、鏈表的倒數第k個結點
1.題目描述
鏈表中倒數第k個結點
輸入一個鏈表，輸出該鏈表中倒數第k個節點，為了符合大多數人的習慣，本題從1開始計數，即鏈表的尾節點是倒數第1個節點，
例如，一個鏈表有 6 個節點，從頭節點開始，它們的值依次是 1、2、3、4、5、6，這個鏈表的倒數第 3 個節點是值為 4 的節點，
2.解題思路
同樣采用快慢指標方法，讓快指標先走k步，結束后快慢指標再次同時出發，快指標結束時慢指標就是走的結果，
代碼如下：
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
struct ListNode
{
int val;
struct ListNode* next;
};
struct ListNode* getKthFromEnd(struct ListNode* head, int k)
{
struct ListNode* fast = head, *slow = head;
while (k--)
{
if (fast == NULL)
{
return NULL;
}
fast = fast->next;
}
while (fast)
{
fast = fast->next;
slow = slow->next;
}
return slow;
}
三、合并兩個排序的鏈表
1.題目描述
合并兩個有序鏈表
將兩個升序鏈表合并為一個新的 升序 鏈表并回傳，新鏈表是通過拼接給定的兩個鏈表的所有節點組成的，
2.解題思路
第一種方法：不帶哨兵位
代碼如下：
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{
//判斷哪個鏈表為空，然后回傳另一個鏈表
if (l1==NULL)
{
return l2;
}
if (l2 == NULL)
{
return l1;
}
struct ListNode* head = NULL, *tail = NULL;
//先去兩個鏈表中小的作為第一個結點
if (l1->next < l2->next)
{
head = tail = l1;
l1 = l1->next;
}
else
{
head = tail = l2;
l2 = l2->next;
}
//去鏈表中其他結點相比較尾插到第一個結點后面
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)
{
tail->next = l1;
}
if (l2)
{
tail->next = l2;
}
return head;
}
第二種方法：帶哨兵位
代碼如下：
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{
struct ListNode* head = NULL, *tail = NULL;
//創建一個哨兵位的頭結點
head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
tail->next = NULL;
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)
{
tail->next = l1;
}
if (l2)
{
tail->next = l2;
}
struct ListNode* node = head;
head = head->next;
free(node);
return head;
}
總結
本文僅僅簡單介紹了鏈表常見的三題，這些題目我們以后可能會遇到，我們務必掌握，另外，如果上述有任何問題，請懂哥指教，不過沒關系，主要是自己能堅持，更希望有一起學習的同學可以幫我指正，但是如果可以請溫柔一點跟我講，愛與和平是永遠的主題，愛各位了，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/277051.html
標籤：其他