目錄
- 19. 洗掉鏈表的倒數第N個節點
- 141. 環形鏈表
19. 洗掉鏈表的倒數第N個節點
給定一個鏈表，洗掉鏈表的倒數第 n 個節點，并且回傳鏈表的頭結點，
暴力解法
另快指標先走n步，慢指標等待快指標停下后隨快指標一起前進，同時用另一指標ret指向慢指標的上一個節點，當快指標指向NULL時，ret正好指向倒數第n+1個結點處，此時可進行洗掉操作，
對于官方解法，可先另一指標指向啞節點，使慢指標從啞節點處開始進行，此操作時間復雜度更少，
struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
struct ListNode* fast = head;
struct ListNode* low = head;
struct ListNode* ret = low;
for(int i=0;i<n;i++) fast = fast->next;
while(fast)
{
ret = low;
fast = fast->next;
low = low->next;
}
if(low == head) return head->next;
ret->next = low->next;
return head;
}
141. 環形鏈表
給定一個鏈表，判斷鏈表中是否有環，
如果鏈表中有某個節點，可以通過連續跟蹤 next 指標再次到達，則鏈表中存在環， 為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）， 如果 pos 是 -1，則在該鏈表中沒有環，注意：pos 不作為引數進行傳遞，僅僅是為了標識鏈表的實際情況，
如果鏈表中存在環，則回傳 true ， 否則，回傳 false ，
bool hasCycle(struct ListNode *head) {
struct ListNode* fast = head;
struct ListNode* low = head;
while(fast && fast->next)
{
fast = fast->next->next;
low = low->next;
if(fast && low && fast->val == low->val)return 1;
}
return 0;
}
其他：
LeetCode解題集——鏈表
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/233949.html
標籤：其他
上一篇：最長公共前綴