### leetcode Brush Title--> 19 Solution (python analysis)

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

Advanced:

Can you try a scan?

Source: LeetCode

Links: leetcode_19.

# 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 # Definition for singly-linked list. class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: def removeNthFromEnd(self, head, n): ''' //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 = [] while head: l.append(head.val) head = head.next # 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) new_head = ListNode(0) 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 # while new_head: # print(new_head.val) # new_head = new_head.next return new_head.next def removeNthFromEnd_1(self, head, n): ''' //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 return head.next if removeNode(head,n)==n else head def removeNthFromEnd_2(self, head, n): ''' //Using a dictionary ''' dummy = ListNode(0) dummy.next = head hash_key = {} head2 = dummy i=0 while head2.next!=None: hash_key[i]=head2 head2 = head2.next i+=1 hash_key[i]=head2 hash_key[i - n ].next = hash_key.get(i-n+2) return dummy.next def removeNthFromEnd_3(self, head, n): ''' //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) dummy.next=head length = 0 first = head # 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 def removeNthFromEnd_4(self, head, n): ''' //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) dummy.next = head 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)