網(wǎng)站首頁 編程語言 正文
反轉(zhuǎn)單鏈表
題目1:給你單鏈表的頭節(jié)點(diǎn)?head
?,請你反轉(zhuǎn)鏈表,并返回反轉(zhuǎn)后的鏈表。
示例 1:
輸入:head = [1,2,3,4,5]
輸出:[5,4,3,2,1]
題目來源:力扣
思路一: 翻轉(zhuǎn)指針方向,首先我們要有三個(gè)指針,這個(gè)就不展示代碼了,邏輯過程如下:
?思路二:頭插方法,我們把每個(gè)節(jié)點(diǎn)拿下來進(jìn)行頭插實(shí)現(xiàn)!代碼實(shí)現(xiàn)如下:
struct ListNode* reverseList(struct ListNode* head) { struct ListNode* cur = head; struct ListNode* newHead = NULL; while (cur) { struct ListNode* next = cur->next; //頭插 cur->next = newHead; newHead = cur; cur = next; } return newHead; }
返回鏈表中間節(jié)點(diǎn)的位置
題目2:給定一個(gè)頭結(jié)點(diǎn)為?head
?的非空單鏈表,返回鏈表的中間結(jié)點(diǎn)。
如果有兩個(gè)中間結(jié)點(diǎn),則返回第二個(gè)中間結(jié)點(diǎn)。
示例 1:
輸入:[1,2,3,4,5,6]
輸出:此列表中的結(jié)點(diǎn) 4 (序列化形式:[4,5,6])
由于該列表有兩個(gè)中間結(jié)點(diǎn),值分別為 3 和 4,我們返回第二個(gè)結(jié)點(diǎn)
題目來源:力扣
思路: 我們使用快慢指針的辦法,快指針fast走兩步,慢指針slow走一步,這樣當(dāng)fast走完了,slow指針就走到了中間的位置,但是我們要注意,如果鏈表節(jié)點(diǎn)為奇數(shù)個(gè)則當(dāng)fast為NULL就應(yīng)該結(jié)束循環(huán),如果鏈表節(jié)點(diǎn)為偶數(shù)個(gè)則當(dāng)fast->next為NULL則結(jié)束循環(huán)!思路解析,代碼實(shí)現(xiàn)如下:
struct ListNode* middleNode(struct ListNode* head) { struct ListNode* slow = head, * fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } return slow; }
合并兩個(gè)有序鏈表
題目3:將兩個(gè)升序鏈表合并為一個(gè)新的 升序 鏈表并返回。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。?
示例 1:
輸入:l1 = [1,2,4], l2 = [1,3,4]
題目來源:力扣
思路:首先我們要判斷兩個(gè)鏈表是否為空,如果為空則返回另一個(gè)鏈表!接著我們需要定義兩個(gè)指針頭指針head和一個(gè)尾指針tail,接著我們比較list1->val是否大于list2->val然后進(jìn)行鏈接鏈表的操作,并且當(dāng)其中一個(gè)鏈表為空則跳出循環(huán),我們則需要在循環(huán)外再次判斷是哪個(gè)鏈表為空導(dǎo)致跳出的循環(huán),并且最后把不為空的鏈表鏈接在后面!最后返回頭指針head!
建議小伙伴們看著這個(gè)思路嘗試著自己寫一下,可以參考如下代碼:
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { if (list1 == NULL) return list2; if (list2 == NULL) return list1; struct ListNode* head = NULL, * tail = NULL; if (list1->val < list2->val) { head = tail = list1; list1 = list1->next; } else { head = tail = list2; list2 = list2->next; } while (list1 != NULL && list2 != NULL) { if (list1->val < list2->val) { //尾插 tail->next = list1; list1 = list1->next; } else { tail->next = list2; list2 = list2->next; } tail = tail->next; } if (list1) tail->next = list1; if (list2) tail->next = list2; return head; }
判斷鏈表中是否有環(huán)
?給你一個(gè)鏈表的頭節(jié)點(diǎn) head ,判斷鏈表中是否有環(huán)。
如果鏈表中存在環(huán)?,則返回 true 。 否則,返回 false 。
示例 1:
輸入:head = [3,2,0,-4], pos = 1
輸出:true
解釋:鏈表中有一個(gè)環(huán),其尾部連接到第二個(gè)節(jié)點(diǎn)。
題目來源:力扣
思路: 我們使用快慢指針的方法,讓fast指針一次走兩步,slow指針一次走一步,當(dāng)鏈表有環(huán)的時(shí)候,當(dāng)slow進(jìn)入環(huán)了,fast就開始追slow,假設(shè)fast跟slow的距離為N,每走一次fast跟slow的距離就會(huì)縮小一步,也就是N-1,N-2,N-3,N-4,直到N為0 fast就追上slow了!代碼實(shí)現(xiàn)如下:
bool hasCycle(struct ListNode *head) { struct ListNode* fast = head; struct ListNode* slow = head; while(fast && fast->next) { slow = slow->next; fast = fast->next->next; if(slow == fast) return true; } return false; }
判斷環(huán)形鏈表進(jìn)入的節(jié)點(diǎn)
給定一個(gè)鏈表的頭節(jié)點(diǎn) ?head?,返回鏈表開始入環(huán)的第一個(gè)節(jié)點(diǎn)。?如果鏈表無環(huán),則返回?null。
不允許修改 鏈表。
示例 1:
輸入:head = [3,2,0,-4], pos = 1
輸出:返回索引為 1 的鏈表節(jié)點(diǎn)
解釋:鏈表中有一個(gè)環(huán),其尾部連接到第二個(gè)節(jié)點(diǎn)。
題目來源:力扣
?思路:我們還是用跟上面一樣的快慢指針的方法,但是在后面,一個(gè)指針從相遇點(diǎn)meet開始走,一個(gè)指針從鏈表頭head開始走,他們會(huì)在入口點(diǎn)相遇!圖解,代碼參考見下:
bool hasCycle(struct ListNode *head) { struct ListNode* fast = head; struct ListNode* slow = head; while(fast && fast->next) { slow = slow->next; fast = fast->next->next; if(slow == fast) return true; } return false; }
??我們一起快樂編程不頭禿!
gitee(碼云):Mercury. (zzwlwp) - Gitee.com? ? ? ?
原文鏈接:https://blog.csdn.net/m0_61784621/article/details/123448745
相關(guān)推薦
- 2022-12-23 C++中關(guān)于union的使用方法說明_C 語言
- 2022-03-23 Android?Camera2開啟自動(dòng)曝光功能_Android
- 2023-01-13 Qt中QList與QLinkedList類的常用方法總結(jié)_C 語言
- 2023-02-25 C和C++如何實(shí)現(xiàn)互相調(diào)用詳解_C 語言
- 2022-06-11 C#實(shí)現(xiàn)文件Move和Copy操作_C#教程
- 2022-06-10 C語言?模擬實(shí)現(xiàn)memcpy與memmove函數(shù)詳解_C 語言
- 2022-07-30 jQuery?UI旋轉(zhuǎn)器部件Spinner?Widget_jquery
- 2022-10-02 詳解R語言caret包trainControl函數(shù)_R語言
- 最近更新
-
- window11 系統(tǒng)安裝 yarn
- 超詳細(xì)win安裝深度學(xué)習(xí)環(huán)境2025年最新版(
- Linux 中運(yùn)行的top命令 怎么退出?
- MySQL 中decimal 的用法? 存儲(chǔ)小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎(chǔ)操作-- 運(yùn)算符,流程控制 Flo
- 1. Int 和Integer 的區(qū)別,Jav
- spring @retryable不生效的一種
- Spring Security之認(rèn)證信息的處理
- Spring Security之認(rèn)證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權(quán)
- redisson分布式鎖中waittime的設(shè)
- maven:解決release錯(cuò)誤:Artif
- restTemplate使用總結(jié)
- Spring Security之安全異常處理
- MybatisPlus優(yōu)雅實(shí)現(xiàn)加密?
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務(wù)發(fā)現(xiàn)-Nac
- Spring Security之基于HttpR
- Redis 底層數(shù)據(jù)結(jié)構(gòu)-簡單動(dòng)態(tài)字符串(SD
- arthas操作spring被代理目標(biāo)對象命令
- Spring中的單例模式應(yīng)用詳解
- 聊聊消息隊(duì)列,發(fā)送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠(yuǎn)程分支