【LintCode 简单】174. 删除链表中倒数第n个节点

本文主要是介绍【LintCode 简单】174. 删除链表中倒数第n个节点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.问题描述：

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

 

2.样例：

Example 1:
    Input: list = 1->2->3->4->5->null， n = 2
    Output: 1->2->3->5->null

Example 2:
    Input:  list = 5->4->3->2->1->null, n = 2
    Output: 5->4->3->1->null

 

3.代码：

"""
Definition of ListNode
class ListNode(object):def __init__(self, val, next=None):self.val = valself.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 herel1 = headcount = 1# 找到最后一个结点while l1.next is not None:l1 = l1.nextcount += 1# 计算应该删除的第几个结点delete = count - n + 1# 处理删除头结点的情况if delete == 1:return head.next# 删除非头结点的情况l1 = headl2 = headwhile delete:if delete == 1:l1.next = l2.nextelse:l1 = l2l2 = l2.nextdelete -= 1# 最后返回headreturn head

思路是先遍历一遍链表计算出链表总共的结点数目，然后就能够知道需要删除的是正向中的第几个结点。然后使用两个指针去循环链表，当第一个指针达到需要删除的结点时，将第二个指针指向第一个指针的下一个结点，就可以完成删除。注意：对头结点删除需要进行特殊处理。

 

这篇关于【LintCode 简单】174. 删除链表中倒数第n个节点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---