Given a linked list, remove the n-th node from the end of list and return its head.

Example 1:

 123 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.

Follow up: Could you do this in one pass?

Related Topics:Linked ListTwo Pointers

## 解題邏輯與實作

### remove

 12345678910111213141516171819202122232425 class Solution: def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode: if not head: return head dummy = ListNode(-1) dummy.next=head result = dummy tmp = head head_len = 0 while tmp: head_len += 1 tmp = tmp.next remove_idx = head_len-n idx = -1 while result: idx += 1 if idx == remove_idx: result.next = result.next.next break result = result.next return dummy.next 

 12345678910111213141516171819202122232425262728 class Solution: def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode: if not head: return head dummy = ListNode(-1) dummy.next = head idx = 0 idx_to_node = {-1: dummy} while head : idx_to_node[idx] = head head = head.next idx +=1 head_len = len(idx_to_node)-1 if head_len == 1: return None remove_idx = head_len - n if remove_idx == head_len-1: idx_to_node[remove_idx-1].next = None else: idx_to_node[remove_idx-1].next = idx_to_node[remove_idx+1] return dummy.next 

### Two Pointers

 12345678910111213141516171819 class Solution: def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode: if not head: return head dummy = ListNode(-1) dummy.next=head prev = dummy cur = dummy while prev and n >= 0: prev = prev.next n -= 1 while prev: prev = prev.next cur = cur.next cur.next = cur.next.next return dummy.next