Leetcode 19. delete the penultimate node of the linked list

Power button | 19. Delete the last of the linked list N Nodes

Title screenshot

 

Method 1 ： Two traversal

The first traversal calculates the length of the linked list to get the length length, And then use it k=length-n Get the location of the node to be deleted .

Second traversal , arrive k Use the location cur.next = cur.next.next Point the node pointer to the next node to be deleted . In this way, you have successfully deleted .

Considering that only one node needs to be deleted , Therefore, a node is set in front of the head node ans, Finally back to ans.next.

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        length, cur = 0, head
        while cur:
            cur = cur.next
            length += 1

        ans = ListNode(0,head)
        cur = ans
        k = length - n
        while k :
            cur = cur.next
            k -= 1
        cur.next = cur.next.next
        return ans.next

Complete test code

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        length, cur = 0, head
        while cur:
            cur = cur.next
            length += 1

        ans = ListNode(0,head)
        cur = ans
        k = length-n
        while k:
            cur = cur.next
            k -= 1
        cur.next = cur.next.next
        return ans.next

def create_linked_list(nums):
    if len(nums) == 0:
        return None
    head = ListNode(nums[0])
    cur = head
    for i in range(1, len(nums)):
        cur.next = ListNode(nums[i])
        cur = cur.next
    return head


def print_linked_list(list_node):
    if list_node is None:
        return

    cur = list_node
    while cur:
        print(cur.val, '->', end=' ')
        cur = cur.next
    print('null')

class main():
    a = Solution()
    nums = [1, 2, 51, 9, 26, 72, 4, 8]
    n = 3
    h = create_linked_list(nums)

    b= a.removeNthFromEnd(head=h,n=n)
    print(nums)
    print(" Delete the last {0} Nodes , The value of this node is {1}".format(n, nums[len(nums)-n]))
    print()
    print(" The result of deleting the linked list is as follows ：")
    print_linked_list(b)

if __name__ == '__main__':
    main()

Method 2 ： Stack

First store the entire linked list on the stack , Then use the characteristics of stack , Take the last element out of the stack . Then find the top element of the stack after it is out of the stack , This node is the previous node of the deleted node , Make this node point to the next node of the deleted node to successfully delete the specified node .

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        ans = ListNode(0,head)
        stack = list()
        cur = ans
        while cur:
            stack.append(cur)
            cur = cur.next

        for i in range(n):
            stack.pop()
        prev = stack[-1]
        prev.next = prev.next.next
        return ans.next

Method 3 ： Double pointer

Use two pointers successively to traverse . There is no need to calculate the length of the linked list .

Because it is required to delete the penultimate list n Nodes , Then the first pointer is ahead of the second pointer n Nodes , Then traverse together , When the first 1 When a pointer reaches the end of the linked list , The second pointer just points to the penultimate n On a node .

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        ans = ListNode(0,head)
        first = head
        for i in range(n):
            first = first.next

        second = ans
        while first:
            first = first.next
            second = second.next

        second.next = second.next.next
        return ans.next