# Title Definition

Given a list of chains, the nth last node of the list is deleted, and the header node of the list is returned.

Example:

Given a list of chains: 1->2->3->4->5, and n = 2.

When the second last node is deleted, the list becomes 1->2->3->5.
Explain:

The given n guarantee is valid.

Can you try a scan?

Source: LeetCode

# Solving problems

This time, there are four methods to use, and there are more on leetcode, which can only be said to be real and brilliant.

## 1. Convert to List and then to Chain List

Convert a list to a list, then a list to a list

## 2. Use recursive thinking

You need your own debug to understand

## 3. Method of using dictionary storage

First, the list is divided into different nodes for storage, then the list is replaced step by step

## 4. Use a single pointer

Define Single Pointer
First calculate the length of the chain table
Then subtracting n from the length of the list is the first node of the node to be erased
Then cycle

## 5. Use double pointer

Define Double Pointer
First let the first pointer go first n steps
Then let first and second go at the same time. When first reaches the end, second also goes to the previous node of the node to be deleted, which is actually a difference between the two.

===================================================

### Realization

```// An highlighted block
class ListNode:
def __init__(self, x):
self.val = x
self.next = None

class Solution:

'''
//It is to turn a list into a list, then delete the values that need to be deleted from the list, and then turn the list into a list (note the shallow and deep copies here)
'''

# boundary value
if not head or n <= 0:
return None

# Convert to List
l = []
# Cross-border prevention
if n > len(l):
return None

# Use pop() to remove the nth last number and convert to a list of chains
l.pop(-n)
p = new_head  # Note that this is a shallow copy   p Changed   new_head Will also change  #Equivalent to a pointer
for j in l:
p.next = ListNode(j)
p = p.next
# Print out results

'''
//recursion
'''
def removeNode(node, n) :
if node.next == None:
return 1

m = removeNode(node.next, n)
if m == n:
if m == 1:
node.next = None
else:
node.next = node.next.next
return m + 1

'''
//Using a dictionary
'''
dummy = ListNode(0)
hash_key = {}
i=0
i+=1

hash_key[i - n  ].next = hash_key.get(i-n+2)

return dummy.next

'''

//Define Single Pointer
//First calculate the length of the chain table
//Then subtracting n from the length of the list is the first node of the node to be erased
//Then cycle
'''
dummy = ListNode(0)
length = 0
# Find out how long the list is
while first:
length+=1
first = first.next

length-=n

first = dummy  # Re-assign first

while length>0:
length-=1  # 2  1
first=first.next

first.next = first.next.next
return dummy.next

'''
//Define Double Pointer
//First let the first pointer go first n steps
//Then let first and second go at the same time. When first reaches the end, second also goes to the previous node of the node to be deleted, which is actually a difference between the two.
'''
dummy = ListNode(0)
first = dummy
second = dummy
# Let first take n steps
for i in range(0,n+1):
first = first.next

while first: #   Seconds and first move forward at the same time. When first comes to the end, second s are the first node location to delete a node
first = first.next
second = second.next

second.next = second.next.next
return dummy.next

def print_node(self,node):

while node:
print(node.val)
node = node.next

a = ListNode(1)
b = ListNode(2)
c = ListNode(3)
d = ListNode(4)
e = ListNode(5)
f = ListNode(6)

a.next = b
b.next = c
c.next = d
d.next = e
e.next = f
s = Solution()

node = s.removeNthFromEnd_1(a,2)
s.print_node(node)
```  Nine original articles published, 0% praised, 166 visits

Keywords: Python

Added by bossman on Sun, 19 Jan 2020 05:50:04 +0200