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)