Given a linked list, delete the NTH node from the bottom of the list and return the head of the list.

Advanced: Can you try using a scan implementation?

The sample1: Enter: head = [1.2.3.4.5], n = 2Output:1.2.3.5]
Copy the code

Method a

The stupid thing to do with an array is to turn it into an array, delete it, and then turn it into a linked list, but still loop twice.

def removeNthFromEnd1(head, n) :
    arr = []
    while not head is None:
        arr.append(head.val)
        head = head.next
    del arr[len(arr) - n]

    if len(arr) == 0: return ListNode()

    for i, value in enumerate(arr[::-1) :if i == 0:
            ans = ListNode(value)
        else:
            ans = ListNode(value, ans)

    return ans
Copy the code

Method 2

Calculate the length of the list reference force link official answer, first calculate the length of the list, then you can determine to delete the penultimate node, is to delete the sequential number of length-n + 1 node. Then one of the deleted nodes points to the next node.

Note also that a common technique for manipulating linked lists is to add a dummy node whose next pointer points to the head node of the list. In this way, we do not need to make special judgments about the head node.

def removeNthFromEnd2(head, n) :
    "" compute the length of the list ""
    def getLength(head) :
        """ Get the list length ""
        length = 0
        while head:
            length += 1
            head = head.next
        return length
    Add a dummy node so that its next points to the head of the list
    dummy = ListNode(0, head)
    length = getLength(head)
    cur = dummy  The current node points to a dummy node
    # the length - n + 1 node is the node we need to delete
    for i in range(1, length - n + 1):
        cur = cur.next
    cur.next = cur.next.next
    return dummy.next
Copy the code

Method three

Stack reference force link official answer, we walk through the linked list at the same time all nodes in order to stack. According to the principle of “first in, last out”, the NTH node we pop out of the stack is the node to be deleted, and the node at the top of the stack is the precursor node of the node to be deleted. In this way, deletion becomes very convenient.

def removeNthFromEnd3(head, n) :
    "" "stack "" "
    dummy = ListNode(0, head)
    stack = list()
    cur = dummy
    while cur:
        stack.append(cur)
        cur = cur.next

    for i in range(n):
        stack.pop()

    prev = stack[-1]
    prev.next = prev.next.next
    return dummy.next
Copy the code

Method four

Since we need to find the NTH to last node, we can use two Pointers, first and second, to traverse the list at the same time, and first is n nodes ahead of second. When first traverses the end of the list, second is exactly the NTH node from the bottom.

It would be easier to delete if we could get the NTH to the last node instead of the NTH to the last node. Therefore, we can consider initially pointing Second at the dummy node, leaving the rest of the operation unchanged. This way, when first traverses the end of the list, the next node of Second is the one we need to delete.

This is the algorithm THAT I think is best, because the scan length is the least.

def removeNthFromEnd4(head, n) :
    """ double pointer, fast and slow pointer ""
    dummy = ListNode(0, head)
    first = head
    second = dummy
    for i in range(n):  Let first lead by n nodes
        first = first.next

    # First and second at the same time
    The sum of the lengths of the for traversal above and the while traversal below adds up to the length L of the list
    while first:
        first = first.next
        second = second.next
    second.next = second.next.next

    return dummy.next
Copy the code
Complexity analysis
  • Time complexity: O(L)O(L)O(L), where L is the length of the linked list.
  • Space complexity: O(1)O(1)O(1), but using constant variables.