【leetcode刷題】20T13-刪除鏈表的倒數第N個節點

• 2020 年 2 月 16 日
• 筆記

木又同學2020年第13篇解題報告

leetcode第19題：刪除鏈表的倒數第N個節點

https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

【題目】

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

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

說明：

給定的 n 保證是有效的。

進階：

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

【思路】

使用兩個指針l1和l2，首先使得l1指向頭結點，l2向後移動n個節點；然後兩個指針同時移動，當l2指向最後一個節點時，即l2.next == None，l1指向倒數第n+1個節點；此時，定義新指針指向l1.next，修改l1.next指向l1.next.next，最後刪除新指針。

注意的是，可能刪除的是頭結點，需要單獨判斷。

【程式碼】

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有效，使得l2後移n個          l1 = l2 = head          for i in range(n):              l2 = l2.next            # 第一個節點          if not l2:              p = head              head = head.next              del(p)              return head            # l1和l2同時移動，l2到達末尾，則l1為倒數第n個          while l2.next:              l1 = l1.next              l2 = l2.next            # 刪除l1.next          p = l1.next          l1.next = p.next          del(p)          return head