【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