19.?刪除鏈表的倒數第N個節點

---

給定一個鏈表，刪除鏈表的倒數第?n?個節點，并且返回鏈表的頭結點。

示例：

給定一個鏈表: 1->2->3->4->5, 和 n = 2.當刪除了倒數第二個節點后，鏈表變為 1->2->3->5.

說明：

給定的?n?保證是有效的。

進階：

你能嘗試使用一趟掃描實現嗎？

這道題難點是在要一趟遍歷實現這個結果，多時間復雜度上有明確的要求，但是在空間復雜度上沒有時間要求，所以我么可以多定義幾個變量來實現，下面是Python實現的代碼。

# -*- coding: utf-8 -*- # Time : 2018/4/1 8:58 # Author : Andy # File : remove_list_end.py # Software: PyCharmclass ListNode:def __init__(self, x):self.val = xself.next = Noneclass Solution:def removeNthFromEnd(self, head, n):p = headp1 = ListNode(-1)p1.next = headhead = p1for i in range(0,n):p = p.nextwhile p != None:p1 = p1.nextp = p.nextp1.next = p1.next.nextreturn head.nextif __name__=="__main__":s = Solution ()head = ListNode(-1)p = headnode = [1,2,3,4,5,6,7,8,9]n = 3for i in node:a = ListNode(i)p.next = ap = p.nextp = s.removeNthFromEnd(head.next,n)while not p == None:print(p.val)p = p.next

代碼中有兩點是整個算法的關鍵處：

1、一次遍歷，利用兩個指針從左到右依次遍歷，一個在前一個在后，兩個指針之間的差距是n，這樣在前面一個指針便利到最后的時候就會出現第一個指針在整個鏈表的倒數第n個節點的前面的位置（為什么會這樣看第二條）。這樣就可以刪除第n個節點了。

2、這兩個指針的初始地址不是在一起的，后面一個指針p指向head，而p1指針是重新定義的一個節點，這個節點的next指向p。這樣就能夠實現p1是p節點的前面一個節點。

3、最后返回的是head節點的next。

總的來說是，系統給的鏈表沒有頭結點，我們自己定義一個頭結點然后返回頭結點的next。

轉載于:https://www.cnblogs.com/andingding-blog/p/8949571.html

總結

以上是生活随笔為你收集整理的LeetCode第19题;删除链表的倒数第N个节点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。