摘要:第題給定一個鏈表,刪除鏈表的倒數第個節點,并且返回鏈表的頭結點。因為,若有一個真正的頭結點,則所有的元素處理方式都一樣。但以第一個有效元素為頭結點,就導致算法的不一致,需要多帶帶處理第一個有效元素頭結點。
leetcode第19題
Given a linked list, remove the n-th node from the end of list and return its head.
給定一個鏈表,刪除鏈表的倒數第 n 個節點,并且返回鏈表的頭結點。
這個題要注意的是:網站定義的鏈表結構head指向第一個有效元素,沒有純正意義上的頭結點,我前兩次提交就是因為這個問題沒過。因為,若有一個真正的頭結點,則所有的元素處理方式都一樣。但以第一個有效元素為頭結點,就導致算法的不一致,需要多帶帶處理第一個有效元素(頭結點)。
題目的額外限制Could you do this in one pass?
你能嘗試使用一趟掃描實現嗎?
還好,題目約束,給定n值一定會是有效的(Given n will always be valid.),這可以少寫好多的邊界判斷。
我的解答(javascript) 思路n值一定有效,又限定在一趟掃描過程中完成,那就是要在掃描的過程中,保存刪除操作的所有信息。很容易想到,鏈表的長度一定大于n,我們迭代處理的是當前元素,故只需要記住當前元素往前的第n+1個元素(即被刪除元素的前一個)就可以了。
鏈接結點定義function ListNode(val) { this.val = val this.next = null; }單鏈接生成器(用于本地測試)
function build(arr) { if(arr.length === 0) //注意:leetcode的空鏈表邏輯是head=null return null let rs = new ListNode(arr[0]) let head = rs for(let i = 1; i < arr.length; i++) { let newOne = new ListNode(arr[i]) rs.next = newOne rs = newOne } return head }本地測試代碼
let rs = removeNthFromEnd(build([1,2,3,4,5]), 2) let cur = rs let str = "" while(cur !== null) { str += `${cur.val} ${cur.next ? "->" : ""} ` cur = cur.next } console.log(str)解答算法
var removeNthFromEnd = function(head, n) { let cur = head //迭代處理當前元素 let m = 0 //偏移量,用來指示要刪除的元素 let del = head //要刪除的元素 while (cur !== null) { if(m > n) { //達到并偏移指示窗口 del = del.next } else { m++ } cur = cur.next } if (del === head && m === n) //注意,刪除頭元素與其它元素是不一樣的 head = head.next //測試用例:[1] 1; [1,2] 2 else del.next = del.next.next return head };leetcode提交結果
Runtime: 56 ms, faster than 100.00% of JavaScript online submissions for Remove Nth Node From End of List.
我的第一個運行速度超過所有提交者的解答,^_^
完整代碼https://github.com/zhoutk/leetcode/blob/master/javascript/qs019_removeNthFromEnd_1.js小結
本文主要標記leetcode中的鏈表結構的特殊性,head直接指向第一個有效元素。
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/100803.html
摘要:給定一個鏈表,刪除鏈表的倒數第個節點,并且返回鏈表的頭結點。示例給定一個鏈表和當刪除了倒數第二個節點后,鏈表變為說明給定的保證是有效的。值得注意的的是,指向應當刪除的節點并無法刪除它,應當指向該刪除節點的前一個節點。 給定一個鏈表,刪除鏈表的倒數第 n 個節點,并且返回鏈表的頭結點。 Given a linked list, remove the n-th node from the ...
摘要:給定一個鏈表,刪除鏈表的倒數第個節點,并且返回鏈表的頭結點。示例給定一個鏈表和當刪除了倒數第二個節點后,鏈表變為說明給定的保證是有效的。值得注意的的是,指向應當刪除的節點并無法刪除它,應當指向該刪除節點的前一個節點。 給定一個鏈表,刪除鏈表的倒數第 n 個節點,并且返回鏈表的頭結點。 Given a linked list, remove the n-th node from the ...
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...
摘要:這題也是攜程年暑假實習生的筆試題。最開始想的解法就是,先循環求鏈表的長度,再用長度,再循環一次就能移除該結點。結果對的,但是超時了。再返回整個鏈表。 Given a linked list, remove the nth node from the end of list and return its head. For example, Given linked list: 1->2...
摘要:雖然時間復雜度還是但是顯然我們可以再一次遍歷中完成這個任務。現在跳出下標的思路,從另一個角度分析。快慢節點之間的距離始終是。當快節點到達終點時,此時的慢節點就是所要刪去的節點。 題目要求 Given a linked list, remove the nth node from the end of list and return its head. For example, ...
閱讀 2591·2021-09-26 10:17
閱讀 3220·2021-09-22 15:16
閱讀 2130·2021-09-03 10:43
閱讀 3258·2019-08-30 11:23
閱讀 3657·2019-08-29 13:23
閱讀 1301·2019-08-29 11:31
閱讀 3686·2019-08-26 13:52
閱讀 1394·2019-08-26 12:22