leetcode题解第19题 Remove Nth Node From End of List（删除链表的倒数第N个节点）

太过爱你忘了你带给我的痛 2022-03-01 13:42 108阅读 0赞

考查列表操作的一道题，题目大意如下：

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

样例输入：

> head = 1->2->3->4->5  
> n = 2

样例输出：

> 1->2->3->5

题目链接：[https://leetcode.com/problems/remove-nth-node-from-end-of-list/][https_leetcode.com_problems_remove-nth-node-from-end-of-list]

emmmm，题目相当简单，所以本来没打算写的，不过交了一发，时间击败了100% python代码，有点特别意义，就简单说一下吧。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Fhcm9uam55_size_16_color_FFFFFF_t_70]

解题思路：

我的想法很简单，先利用指针遍历一下链表，计算链表的长度length。

然后从头开始，将指针移动到length-n-1的位置，改变一下节点的Next的值就行了。

样例代码：

class Solution(object):
        def list_len(self, head):
            """ 计算给定链表的长度 :param head: :return: """
            tmp_head = head
            cnt = 0
            while tmp_head:
                cnt += 1
                tmp_head = tmp_head.next
            return cnt
    
        def removeNthFromEnd(self, head, n):
            """ :type head: ListNode :type n: int :rtype: ListNode """
            # 获取链表的长度
            length = self.list_len(head)
            # 长度为1，移除完就没了，返回None
            if length == 1:
                return None
            # 长度为n的话，相当于移除了头结点，直接返回head.next即可
            if length == n:
                return head.next
            # 否则的话，先找到倒数第n个节点的前一个节点
            tmp_head = head
            for i in range(length - n - 1):
                tmp_head = tmp_head.next
            # 然后通过改变next指向，移除掉倒数第n个节点即可。
            remove_node = tmp_head.next
            next_node = remove_node.next
            tmp_head.next = next_node
            return head

转载请注明出处：[https://blog.csdn.net/aaronjny/article/details/88747002][https_blog.csdn.net_aaronjny_article_details_88747002]

[https_leetcode.com_problems_remove-nth-node-from-end-of-list]: https://leetcode.com/problems/remove-nth-node-from-end-of-list/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Fhcm9uam55_size_16_color_FFFFFF_t_70]: /images/20220301/b57f87ce2d31452696e3010a5e95ddb6.png
[https_blog.csdn.net_aaronjny_article_details_88747002]: https://blog.csdn.net/aaronjny/article/details/88747002