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新闻热点
疑难解答
