摘要:遞歸法復雜度時間空間思路當遞歸到鏈表尾部時返回,每次返回時長度加,一旦長度為時記錄下該節點。雙指針法復雜度時間空間思路用兩個指針,快指針先走步,然后快慢指針同時開始走,保持的距離,這樣當快指針到達末尾時,慢指針就是倒數第個。
Nth to Last Node in List
遞歸法 復雜度Find the nth to last element of a singly linked list.
The minimum number of nodes in list is n.
時間 O(N) 空間 O(N)
思路當遞歸到鏈表尾部時返回,每次返回時長度加1,一旦長度為N時記錄下該節點。
雙指針法 復雜度時間 O(N) 空間 O(1)
思路用兩個指針,快指針先走N步,然后快慢指針同時開始走,保持N的距離,這樣當快指針到達末尾時,慢指針就是倒數第N個。
代碼public class Solution { ListNode nthToLast(ListNode head, int n) { // write your code here ListNode slow = head; ListNode fast = head; while(n-- > 0){ fast = fast.next; } while(fast != null){ fast = fast.next; slow = slow.next; } return slow; } }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/64520.html
摘要:依然是一道找倒數第個結點的鏈表題,用雙指針做。先走,然后和一起走,直到為,的位置就是倒數第個位置。 Problem Find the nth to last element of a singly linked list. The minimum number of nodes in list is n. Example Given a List 3->2->1->5->null ...
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...
摘要:給定一個鏈表,刪除鏈表的倒數第個節點,并且返回鏈表的頭結點。示例給定一個鏈表和當刪除了倒數第二個節點后,鏈表變為說明給定的保證是有效的。值得注意的的是,指向應當刪除的節點并無法刪除它,應當指向該刪除節點的前一個節點。 給定一個鏈表,刪除鏈表的倒數第 n 個節點,并且返回鏈表的頭結點。 Given a linked list, remove the n-th node from the ...
摘要:給定一個鏈表,刪除鏈表的倒數第個節點,并且返回鏈表的頭結點。示例給定一個鏈表和當刪除了倒數第二個節點后,鏈表變為說明給定的保證是有效的。值得注意的的是,指向應當刪除的節點并無法刪除它,應當指向該刪除節點的前一個節點。 給定一個鏈表,刪除鏈表的倒數第 n 個節點,并且返回鏈表的頭結點。 Given a linked list, remove the n-th node from the ...
摘要:雖然時間復雜度還是但是顯然我們可以再一次遍歷中完成這個任務。現在跳出下標的思路,從另一個角度分析。快慢節點之間的距離始終是。當快節點到達終點時,此時的慢節點就是所要刪去的節點。 題目要求 Given a linked list, remove the nth node from the end of list and return its head. For example, ...
閱讀 1402·2021-10-14 09:43
閱讀 992·2021-09-10 10:51
閱讀 1443·2021-09-01 10:42
閱讀 2189·2019-08-30 15:55
閱讀 586·2019-08-30 15:55
閱讀 2339·2019-08-30 14:21
閱讀 1715·2019-08-30 13:04
閱讀 3467·2019-08-29 13:09