PRoblem:
Given a linked list, remove the nth node from the end of list and 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.
Idea: 1. 用空間換時間方法。從head開始遍歷單向鏈表，把每一項放入數組中（此時存放的都是鏈表節點的引用）。遍歷完畢后，計算數組的大小（即單向鏈表的長度），然后用總長度減去n，可得需要移除的項的下標。然后直接訪問數組中該下標，修改對應以及臨近節點的值即可。 2. n ahead。設置兩個游標，其中fast游標比slow游標快n個節點。當fast游標到達鏈表末端時，slow游標所指的節點就是待刪節點。 3. 遞歸法。先通過遞歸調用index()函數找到末節點的值，然后把倒數第n個節點之前的節點值往后挪一個位置：“node.next.val = node.val”以下是摘抄自作者：
Value-Shifting - AC in 64 ms
My first solution is “cheating” a little. Instead of really removing the nth node, I remove the nth value. I recursively determine the indexes (counting from back), then shift the values for all indexes larger than n, and then always drop the head.
Solution: 1.
class Solution(object): def removeNthFromEnd(self, head, n): nodelist = [] if head == None: return tmpnode = head while tmpnode.next != None: nodelist.append(tmpnode) tmpnode = tmpnode.next nodelist.append(tmpnode) lenlist = len(nodelist) targetindex = lenlist - n if targetindex == 0: if lenlist == 1: return None else: head = nodelist[1] elif targetindex == lenlist - 1: nodelist[lenlist-2].next = None else: nodelist[targetindex-1].next = nodelist[targetindex+1] return head2. class Solution: def removeNthFromEnd(self, head, n): fast = slow = head for _ in range(n): fast = fast.next if not fast: return head.next while fast.next: fast = fast.next slow = slow.next slow.next = slow.next.next return head3.
class Solution: def removeNthFromEnd(self, head, n): def index(node): if not node: return 0 i = index(node.next) + 1 if i > n: node.next.val = node.val return i index(head) return head.next新聞熱點
疑難解答
