首页 > itarticle > l19 remove nth node from end of list

l19 remove nth node from end of list

admin 11月 13, 2020 0

题目描述

Given a linked list, remove the nth node from the end of list and return its head.

For example,

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

   After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Try to do this in one pass.

解题思路

先获取List的长度，获取需要删除的第n个节点的前一个节点
如果当前节点是head，返回head.next
否则，将prev.next设置为current.next

Python实现1

class (object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        if not head:
            return None
        current = head
        length = 0
        while current:
            length+=1
            current = current.next

        if n>=length:
            n = n%length
        else:
            n = length-n

        current = head
        idx = 0
        prev = current
        while idx<n:
            prev = current
            current = current.next
            idx+=1
        if current != head:
            prev.next = current.next
            return head
        else:
            return head.next

Runtime: 59 ms