leetcode之-题19

题目

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.

题解

思路

使用两个指针,两个指针相隔n-1,每次两个指针向后一步,当后面一个指针没有后继了,前面一个指针就是要删除的节点 注意:可能会出现只有1个节点,同时n=1的情况,这时指针没有后继节点

python代码

# 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
        """
        """
        采用双指针思想,两个指针相隔n-1,每次两个指针向后一步,当后面一个指针没有后继了,前面一个指针就是要删除的节点
        """
        p = head
        q = head
        Ppre = None
        for x in xrange(0, n-1):
            q = q.next
        while q.next is not None:
            Ppre = p
            p = p.next
            q = q.next
        # 出现[1],n=1的情况下,Ppre依然为None
        if Ppre == None:
            head = p.next
        else:
            Ppre.next = p.next
        return head    

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏HansBug's Lab

2243: [SDOI2011]染色

2243: [SDOI2011]染色 Time Limit: 20 Sec  Memory Limit: 512 MB Submit: 3113  Solved...

2649
来自专栏数据结构与算法

SPOJ COT2 - Count on a tree II(树上莫队)

1423
来自专栏落花落雨不落叶

leetcode 34. Search for a Range

2676
来自专栏landv

c语言-三字符组

1705
来自专栏JackeyGao的博客

Leetcode 算法 -3. Longest Substring Without Repeating Characters

我们以ababcbb为例说明, 这里hash表的值-1是初始值, 这样在方便做+1操作. index 作为开始索引值, 起初index为0, 这是理所当然的。当...

382
来自专栏Linux驱动

22.C++- 继承与组合,protected访问级别

在C++里,通过继承和组合实现了代码复用,使得开发效率提高,并且能够通过代码看到事物的关系 组合比继承简单,所以在写代码时先考虑能否组合,再来考虑继承. ---...

2695
来自专栏数据结构与算法

1230 元素查找

1230 元素查找 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题目描述 Description 给出...

1843
来自专栏mySoul

C++ 面向对象 一

使用内联函数的时候,编译器会进行自动替换,即类似于C语言中的宏。以减少入栈和出栈的操作。

463
来自专栏琦小虾的Binary

map 学习(下)——C++ 中的 hash_map, unordered_map

map 学习(下)——C++ 中的 hash_map, unordered_map 接上篇《map 学习(一)——C++中 map 的使用》。 一、hash_m...

9217
来自专栏计算机视觉与深度学习基础

Leetcode 90 Subsets II

Given a collection of integers that might contain duplicates, nums, return all ...

1848

扫码关注云+社区