首页 > 代码库 > LintCode Python 简单级题目 174.删除链表中倒数第n个节点

LintCode Python 简单级题目 174.删除链表中倒数第n个节点

题目描述:

 

给定一个链表,删除链表中倒数第n个节点,返回链表的头节点。

 注意事项

链表中的节点个数大于等于n

您在真实的面试中是否遇到过这个题? 
Yes

 

样例

给出链表1->2->3->4->5->null和 n = 2.

删除倒数第二个节点之后,这个链表将变成1->2->3->5->null.

 

挑战 

O(n)时间复杂度

 

标签 
两根指针 链表

 

题目分析:

 

创建两个指针,head指向表头、curent指向链表第n个元素;

循环后移n次,直至curent=Null,此时head指向倒数第n个元素。

O(n)时间复杂度

 

源码:

"""
Definition of ListNode
class ListNode(object):

    def __init__(self, val, next=None):
        self.val = val
        self.next = next
"""
class Solution:
    """
    @param head: The first node of linked list.
    @param n: An integer.
    @return: The head of linked list.
    """
    def removeNthFromEnd(self, head, n):
        # write your code here
        if head is None: return None
        if n == 0: return head
        cur = head
        follow = head
        pre = head
        for i in range(n):
            follow = follow.next
        # 当follow为null时,此时链表长度等于n,删除第一个元素即可
        if follow is None:
            return cur.next
        # 将pre和fol依次后移,实际后移次数为n-1    
        while follow.next is not None:
            follow = follow.next
            cur = pre
            pre = pre.next
        # 删除第n个元素
        pre.next = pre.next.next
        return head

  

LintCode Python 简单级题目 174.删除链表中倒数第n个节点