刪除鏈表的倒數(shù)第N個節(jié)點

題目

給定一個鏈表，刪除鏈表的倒數(shù)第 n 個節(jié)點，并且返回鏈表的頭結(jié)點。

• 示例：

  給定一個鏈表: 1->2->3->4->5, 和 n = 2.
  
  當(dāng)刪除了倒數(shù)第二個節(jié)點后，鏈表變?yōu)?1->2->3->5.
  

說明：

給定的 n 保證是有效的。

進階：

你能嘗試使用一趟掃描實現(xiàn)嗎？

解答

• 思路：

  • 用雙指針法；
  • 首先讓一個right指針，先指向第n + 1個節(jié)點，讓一個left指針指向頭節(jié)點；
  • 然后讓兩個指針一起右移，直到right指針為None停止；（過程中使用pre指針記錄left指針的左邊節(jié)點，初始pre為None）
  • 最后刪除left指向的那個節(jié)點即可。

• 代碼：

  def removeNthFromEnd(self, head, n):
      """
      :type head: ListNode
      :type n: int
      :rtype ListNode
  
      (knowledge)
  
      思路：
      1. 用雙指針法；
      2. 首先讓一個right指針，先指向第n + 1個節(jié)點，讓一個left指針指向頭節(jié)點；
      3. 然后讓兩個指針一起右移，直到right指針為None停止；（過程中使用pre指針記錄left指針的左邊節(jié)點，初始pre為None）
      4. 最后刪除left指向的那個節(jié)點即可
      """
      pre, left, right = None, head, head
  
      # 首先讓right指針指向第n + 1個節(jié)點
      for i in range(n):
          right = right.next
  
      # left和right兩個指針一起右移，同時使用pre記錄left指針的左邊節(jié)點
      while right:
          pre, left, right = left, left.next, right.next
  
      if not pre: # 處理要刪除的節(jié)點是頭節(jié)點的情況
          return head.next
      else:
          pre.next = left.next
          return head
  

測試驗證

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
    
    def __repr__(self):
        if self:
            return "{}->{}".format(self.val, repr(self.next))

class Solution:
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype ListNode

        (knowledge)

        思路：
        1. 用雙指針法；
        2. 首先讓一個right指針，先指向第n + 1個節(jié)點，讓一個left指針指向頭節(jié)點；
        3. 然后讓兩個指針一起右移，直到right指針為None停止；（過程中使用pre指針記錄left指針的左邊節(jié)點，初始pre為None）
        4. 最后刪除left指向的那個節(jié)點即可
        """
        pre, left, right = None, head, head

        # 首先讓right指針指向第n + 1個節(jié)點
        for i in range(n):
            right = right.next

        # left和right兩個指針一起右移，同時使用pre記錄left指針的左邊節(jié)點
        while right:
            pre, left, right = left, left.next, right.next

        if not pre: # 處理要刪除的節(jié)點是頭節(jié)點的情況
            return head.next
        else:
            pre.next = left.next
            return head


if __name__ == '__main__':
    solution = Solution()
    head = ListNode(1)
    head.next = ListNode(2)
    head.next.next = ListNode(3)
    head.next.next.next = ListNode(4)
    head.next.next.next.next = ListNode(5)
    print(solution.removeNthFromEnd(head, 2), "= 1->2->3->5")