leetcode | 19.删除链表中的倒数第N个节点

19. 删除链表中的倒数第N个节点

题目描述

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

题目链接

思路

1. 计算链表长度
   删除链表的倒数第 n 个结点操作就等价于删除正数第L-n+1个节点，L为链表的长度

2. 栈
   遍历链表的同时将所有节点依次入栈，根据栈 先进后出 的原则，弹出栈的第n个节点就是需要删除的节点，并且弹出
   第n个节点后的栈顶节点为待删除节点的前驱节点。

   代码

   class ListNode(object):

    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
   

   class Solution(object):

    def removeNthFromEnd(self, linkedList, n):
        """
        计算链表长度
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        dummy = ListNode(0, linkedList)
        length = self.lenOfLinkedList(dummy)
        print(length)
        cur = dummy
        for i in range(1, length - n):
            cur = cur.next
        cur.next = cur.next.next
        return dummy.next
    
    def removeNthFromEnd2(self, head, n):
        """栈"""
        stack = list()
        cur = head
        while cur:
            stack.append(cur)
            cur = cur.next
        for i in range(n):
            stack.pop()
            
        prev = stack[-1]
        prev.next = prev.next.next
        return head
    
    def removeNthFromEnd3(self, head, n):
        """双指针"""
        dummy = ListNode(0, head)
        first = head
        second = dummy
        for i in range(n):
            first = first.next
        
        while first:
            first = first.next
            second = second.next
        
        second.next = second.next.next
        return dummy.next
    
    def lenOfLinkedList(self, head):
        if not head:
            return 0
        p = head
        count = 0
        while p is not None:
            count += 1
            p = p.next
        return count
    
    def createLinkedList(self, list):
        head = r = ListNode(list[0])
        for num in list[1:]:
            node = ListNode(num)
            r.next = node
            r = node
        
        return head
    
    def traverseLinkedList(self, head):
        if not head:
            return
        p = head
        while p is not None:
            print(p.val, end=" ")
            p = p.next
        print("")
   

   if name == “main“:

    slt = Solution()
    linkedList = slt.createLinkedList([1, 2, 3, 4, 5])
    print("linked list:", end="")
    slt.traverseLinkedList(linkedList)
    length = slt.lenOfLinkedList(linkedList)
    print("length of linked list:", length)
    # newLinkedList = slt.removeNthFromEnd(linkedList, 2)
    # newLinkedList = slt.removeNthFromEnd2(linkedList, 2)
    newLinkedList = slt.removeNthFromEnd3(linkedList, 2)
    print("linked list after deleting the reversed n-th node:", end="")
    slt.traverseLinkedList(newLinkedList)