Delete the penultimate node of the linked list

The title

Given a linked list, delete the NTH last node of the list and return the first node of the list.

Example:

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

When the penultimate node is deleted, the linked list becomes 1->2->3->5.

A given n is guaranteed to be valid.

Advanced:

Can you try using a scan implementation?

knowledge

The problem solving

  1. You just walk through it once and you know what the value of the NTH value is.
  2. The intuitive idea is: first walk through to know the total number M, and then walk again, walk m-N steps to go to the previous node to delete the node can be deleted.
  3. Better: use two Pointers p1,p2, p1 goes n steps first, then together, and when P1 reaches the last node (p1->next is None), P2 goes exactly before the node to be deleted.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """ :type head: ListNode :type n: int :rtype: ListNode """
        h1 = head
        h2 = head

        for i in range(n):
            h1 = h1.next

        while h1.next is not None:
            h1 = h1.next
            h2 = h2.next

        h2.next = h2.next.next
        return head
Copy the code
  1. Bugs with this solution:If you delete the first item in the list, then p1 takes n steps first and ends up being h1=Noneh1.nextI’m going to make a mistake.
  2. And if you delete the first node, it doesn’t pass eitherh2.next = h2.next.nextThe implementation.
  3. You can add dummy nodes to the head in this case or return directly to head.next
    if h1 is None:
        return head.next
Copy the code
  1. Method of adding dummy nodes: P1 goes to n+1 first. When P1 goes to None, P2 goes to the previous node of the truncated node. After deleting the node, p2 returns to the next node of the dummy node
class Solution(object):
    def removeNthFromEnd(self, head, n):
        """ :type head: ListNode :type n: int :rtype: ListNode """
        h = ListNode(0)
        h.next = head

        h1 = h
        h2 = h

        for i in range(n + 1):
            h1 = h1.next
        
        while h1 is not None:
            h1 = h1.next
            h2 = h2.next

        h2.next = h2.next.next
        return h.next
Copy the code