資訊專欄INFORMATION COLUMN
摘要：先用快指針向前走步，這樣快指針就領(lǐng)先慢指針步了，然后快慢指針一起走，當(dāng)快指針到盡頭時(shí)，慢指針就是倒數(shù)第個(gè)。注意因?yàn)橛锌赡軇h除頭節(jié)點(diǎn)，我們需要一個(gè)代碼快指針先走步從開始慢指針和快指針一起走刪除當(dāng)前的下一個(gè)節(jié)點(diǎn)
Remove Nth Node From End of List 最新更新的解法和思路：https://yanjia.me/zh/2018/11/...
Given a linked list, remove the nth node from the end of list and迭代法 復(fù)雜度
return its head.For example,
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list
becomes 1->2->3->5. Note: Given n will always be valid. Try to do this
in one pass.
時(shí)間 O(N) 空間 O(1)
思路典型的快慢指針。先用快指針向前走n步，這樣快指針就領(lǐng)先慢指針n步了，然后快慢指針一起走，當(dāng)快指針到盡頭時(shí)，慢指針就是倒數(shù)第n個(gè)。不過如果要?jiǎng)h除這個(gè)節(jié)點(diǎn)，我們要知道的是該節(jié)點(diǎn)的前面一個(gè)節(jié)點(diǎn)。另外，如果要?jiǎng)h的是頭節(jié)點(diǎn)，也比較難處理。這里使用一個(gè)dummy頭節(jié)點(diǎn)，放在本來的head之前，這樣我們的慢指針從dummy開始遍歷，當(dāng)快指針為空是，慢指針正好是倒數(shù)第n個(gè)的前一個(gè)節(jié)點(diǎn)。最后返回的時(shí)候，返回dummy的下一個(gè)。
注意因?yàn)橛锌赡軇h除頭節(jié)點(diǎn)，我們需要一個(gè)dummyhead
代碼java
public class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode fast = head;
ListNode dummy = new ListNode(0);
dummy.next = head;
// 快指針先走n步
for(int i = 0; i < n; i++){
fast = fast.next;
}
// 從dummy開始慢指針和快指針一起走
ListNode curr = dummy;
while(fast != null){
fast = fast.next;
curr = curr.next;
}
// 刪除當(dāng)前的下一個(gè)節(jié)點(diǎn)
curr.next = curr.next.next;
return dummy.next;
}
}
python
class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
dummy = ListNode(0)
dummy.next = head
fast = dummy
for i in range(0, n):
fast = fast.next
slow = dummy
while(fast.next is not None):
slow = slow.next
fast = fast.next
slow.next = slow.next.next
return dummy.next
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64594.html
摘要：雖然時(shí)間復(fù)雜度還是但是顯然我們可以再一次遍歷中完成這個(gè)任務(wù)。現(xiàn)在跳出下標(biāo)的思路，從另一個(gè)角度分析?？炻?jié)點(diǎn)之間的距離始終是。當(dāng)快節(jié)點(diǎn)到達(dá)終點(diǎn)時(shí)，此時(shí)的慢節(jié)點(diǎn)就是所要?jiǎng)h去的節(jié)點(diǎn)。 題目要求 Given a linked list, remove the nth node from the end of list and return its head. For example, ...
摘要：第題給定一個(gè)鏈表，刪除鏈表的倒數(shù)第個(gè)節(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)。因?yàn)?，若有一個(gè)真正的頭結(jié)點(diǎn)，則所有的元素處理方式都一樣。但以第一個(gè)有效元素為頭結(jié)點(diǎn)，就導(dǎo)致算法的不一致，需要單獨(dú)處理第一個(gè)有效元素頭結(jié)點(diǎn)。 leetcode第19題 Given a linked list, remove the n-th node from the end of list and return its h...
摘要：移除鏈表倒數(shù)第個(gè)元素給定一個(gè)鏈表，移除倒數(shù)第個(gè)元素，返回鏈表頭部。 移除鏈表倒數(shù)第n個(gè)元素 Remove Nth Node From End of List 給定一個(gè)鏈表，移除倒數(shù)第n個(gè)元素，返回鏈表頭部。 Given a linked list, remove the nth node from the end of list and return its head. Note:...
摘要：題目詳情題目要求輸入一個(gè)和一個(gè)數(shù)字。要求我們返回刪掉了倒數(shù)第個(gè)節(jié)點(diǎn)的鏈表。想法求倒數(shù)第個(gè)節(jié)點(diǎn)，我們將這個(gè)問題轉(zhuǎn)化一下。我們聲明兩個(gè)指針和，讓和指向的節(jié)點(diǎn)距離差保持為。解法使點(diǎn)和點(diǎn)的差距為同時(shí)移動(dòng)和使得到達(dá)的末尾刪除倒數(shù)第個(gè)節(jié)點(diǎn) 題目詳情 Given a linked list, remove the nth node from the end of list and return it...
Problem Given a linked list, remove the nth node from the end of list and return its head. Example Given linked list: 1->2->3->4->5->null, and n = 2. After removing the second node from the end, the l...
閱讀 881·2021-11-22 09:34
閱讀 1017·2021-10-08 10:16
閱讀 1832·2021-07-25 21:42
閱讀 1800·2019-08-30 15:53
閱讀 3531·2019-08-30 13:08
閱讀 2191·2019-08-29 17:30
閱讀 3353·2019-08-29 17:22
閱讀 2184·2019-08-29 15:35
