移除链表倒数第n个元素

yhaolpz 发布于2019-07-25 12:04 / 1121人阅读

摘要：移除链表倒数第个元素给定一个链表，移除倒数第个元素，返回链表头部。

移除链表倒数第n个元素 Remove Nth Node From End of List

给定一个链表，移除倒数第n个元素，返回链表头部。

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

Note:
Given n will always be valid.
Try to do this in one pass.

example 1

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.

example 2

Given linked list: 1, and n = 1.
output: None

example 3

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

思路

两个指针，fast和slow，fast指向slow之后n个位置，同步移动fast和slow，当fast.next为null的时候，slow.next即为要移除的那个元素，只需要slow.next = slow.next.next即可，时间复杂度O(n)

注意考虑n为链表长度的情况，即移除首个元素

代码

# Definition for singly-linked list.
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
        """
        a = b = head
        for i in range(n):
            b = b.next
        if not b:
            return head.next
        while b.next:
            a = a.next
            b = b.next
        a.next = a.next.next
        return head

本题以及其它leetcode题目代码github地址: github地址

海外云主机私有云倒数第二条记录移除元素移除数组元素 js 数据移除元素

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/38664.html

LeetCode 203：移除链表元素 Remove LinkedList Elements

摘要：删除链表中等于给定值的所有节点。链表的删除操作是直接将删除节点的前一个节点指向删除节点的后一个节点即可。这就无需考虑头节点是否为空是否为待删除节点。删除链表中等于给定值 val 的所有节点。 Remove all elements from a linked list of integers that have value val. 示例: 输入: 1->2->6->3->4->5-...

hzc 2019-08-16 18:37 评论0 收藏0
LeetCode 203：移除链表元素 Remove LinkedList Elements

摘要：删除链表中等于给定值的所有节点。链表的删除操作是直接将删除节点的前一个节点指向删除节点的后一个节点即可。这就无需考虑头节点是否为空是否为待删除节点。删除链表中等于给定值 val 的所有节点。 Remove all elements from a linked list of integers that have value val. 示例: 输入: 1->2->6->3->4->5-...

makeFoxPlay 2019-07-31 11:28 评论0 收藏0
LeetCode【203】：移除链表元素

摘要：题目描述删除链表中等于给定值的所有节点。示例输入输出非递归解法思路遍历链表，找出每个待删除节点的前一个节点。特殊情况第一个节点就是待删除节点时，要单独操作。注意点当输入为时，按上面的思路删除第一个节点，剩下的链表的头节点又是待删除节点。题目描述删除链表中等于给定值 val 的所有节点。示例输入: 1->2->6->3->4->5->6, val = 6输出: 1->2->3->...

wwolf 2019-08-19 11:38 评论0 收藏0
准备下次编程面试前你应该知道的数据结构

摘要：以下内容编译自他的这篇准备下次编程面试前你应该知道的数据结构瑞典计算机科学家在年写了一本书，叫作算法数据结构程序。国外 IT 教育学院 Educative.io 创始人 Fahim ul Haq 写过一篇过万赞的文章《The top data structures you should know for your next coding interview》,总结了程序员面试中需要掌...

desdik 2019-08-23 14:57 评论0 收藏0