动图：删除链表的倒数第N个结点

本文转载自微信公众号「程序员小熊」，作者Dine。转载本文请联系程序员小熊公众号。

成都创新互联成立以来不断整合自身及行业资源、不断突破观念以使企业策略得到完善和成熟，建立了一套“以技术为基点，以客户需求中心、市场为导向”的快速反应体系。对公司的主营项目，如中高端企业网站企划 / 设计、行业 / 企业门户设计推广、行业门户平台运营、成都app软件开发公司、移动网站建设、微信网站制作、软件开发、雅安服务器托管等实行标准化操作，让客户可以直观的预知到从成都创新互联可以获得的服务效果。

本文主要介绍一道面试中常考链表删除相关的题目，即 leetcode 19. 删除链表的倒数第 N 个结点。采用双指针 + 动图的方式进行剖析，供大家参考，希望对大家有所帮助。

删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

进阶：你能尝试使用一趟扫描实现吗?

解题思路

在链表中要删除某个节点 nodeB，必须先找到 nodeB 的前一节点 nodeA ，再将 nodeA 指向 nodeB 的下一节点 nodeC ，从而实现节点 nodeB 的删除。

例如要删除链表 L(1->2->3->4->5) 中值为 3 的节点，首先得找到该节点的前一节点(值为 2 的节点)，才能实现该节点的删除，如下图示：

题目要求删除倒数第 n 个节点，所以首先得找到该节点的前一节点，但由于不知道整个链表的长度，因此不知道待删除的节点是正数的第几个节点，所以很难从头节点开始遍历时删除掉这个节点。

思路一

先遍历一遍链表，获取整个链表的长度;假设整个链表的长度为 l，则可知要删除的节点为第 l - n + 1 个节点;再遍历一遍，删除倒数第 n 个节点。例如链表 L 为 1->2->3->4->5，n = 3，则要删除的节点为第 5 - 3 + 1 = 3 个节点。

思路二

尽管思路一可行，但是需要遍历链表两遍，不够简洁，而且题目的进阶中也提到尝试使用一趟扫描实现，因此本文采用双指针的策略，实现通过一次扫描删除倒数第 n 个节点。

在上一期链表相关专题虚拟头节点秒杀链表问题中提到增加虚拟头节点的策略解决链表问题，增加虚拟头节点的好处在于：不需要单独考虑头节点，这样对头节点的处理就像跟其它节点一样。本文也同样采用这种策略。

举栗

以链表 1->2->3->4->5，n = 3 为栗，如下如示。

按照上面分析，先要找到倒数第 3 个节点的前一节点，即值为 2 的节点;

增加虚拟头节点

值为 2 的节点是倒数第 4 个节点(后往前数)，增加两指针 fast/slow，分别指向最后一个元素(NULL)和上图中 target 的位置;

此时 fast 跟 slow 之间的间距是固定(n = 3)的，找到 target(slow)后，只需要删除其下一节点即可，但 slow 指向的节点前面有多少个节点该如何确定呢?

由于当前已知 fast 和 slow 指向节点之间的长度是固定的，只需要将这两个指针向前挪，直到 slow 挪到虚拟头节点(值为 0)的位置，此时 fast 指向值为 4 的节点的位置，fast 只需要由虚拟头节点的位置右移 n + 1 = 4 即可。如下图示：

当 fast 右移至值为 4 的节点时，指针 slow 和 fast 同时右移，直至 fast 移到 NULL，此时 slow 刚好到 target 位置，即指向倒数第 n + 1 个节点，如下图示。

Show me the Code

c++

 
 
 
 
  
  
  
  ListNode* removeNthFromEnd(ListNode* head, int n) { 
  
  
  
      ListNode* dummyHead = new ListNode(0); 
  
  
  
      dummyHead->next = head; 
  
  
  
      ListNode *slow = dummyHead, *fast = dummyHead; 
  
  
  
      for (int i = 0; i < n + 1; ++i) { 
  
  
  
          fast = fast->next; 
  
  
  
      } 
  
  
  
   
  
  
  
      while (fast != NULL) { 
  
  
  
          slow = slow->next; 
  
  
  
          fast = fast->next; 
  
  
  
      } 
  
  
  
   
  
  
  
      ListNode* delNode = slow->next; 
  
  
  
      slow->next = delNode->next; 
  
  
  
      delete delNode; 
  
  
  
   
  
  
  
      ListNode* retNode = dummyHead->next; 
  
  
  
      delete dummyHead; 
  
  
  
   
  
  
  
      return retNode; 
  
  
  
  }

java

 
 
 
 
  
  
  
  ListNode removeNthFromEnd(ListNode head, int n) { 
  
  
  
      ListNode dummyHead = new ListNode(0); 
  
  
  
      dummyHead.next = head; 
  
  
  
      ListNode slow = dummyHead, fast = dummyHead; 
  
  
  
      for (int i = 0; i < n + 1; ++i) { 
  
  
  
          fast = fast.next; 
  
  
  
      } 
  
  
  
   
  
  
  
      while (fast != null) { 
  
  
  
          slow = slow.next; 
  
  
  
          fast = fast.next; 
  
  
  
      } 
  
  
  
   
  
  
  
      slow.next = slow.next.next; 
  
  
  
      return dummyHead.next; 
  
  
  
  }

当前文章：动图：删除链表的倒数第N个结点
链接URL：http://www.stwzsj.com/qtweb/news48/9648.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源：创新互联

猜你还喜欢下面的内容