每日：删除链表倒数第N个结点

本文转载自微信公众号「三分钟学前端」，作者sisterAn。转载本文请联系三分钟学前端公众号。

创新互联公司主要业务有网站营销策划、成都网站建设、成都做网站、微信公众号开发、小程序设计、HTML5、程序开发等业务。一次合作终身朋友，是我们奉行的宗旨；我们不仅仅把客户当客户，还把客户视为我们的合作伙伴，在开展业务的过程中，公司还积累了丰富的行业经验、营销型网站建设资源和合作伙伴关系资源，并逐渐建立起规范的客户服务和保障体系。 

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

示例：

 
 
 

  
  
  
给定一个链表: 1->2->3->4->5, 和 n = 2. 
  
  
  
当删除了倒数第二个节点后，链表变为 1->2->3->5. 
 
 
 

说明：

给定的 n 保证是有效的。

进阶：

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

解法：快慢指针

解题思路： 需要删除链表中的倒数第 n 个节点，我们需要知道的就是倒数第 n+1 个节点，然后删除删除倒数第 n+1 节点的后继节点即可

步骤：

使用 2 个指针：

• fast 快指针提前走 n+1 步
• slow 指针指向当前距离 fast 倒数第 n 个节点， 初始为 head

然后， fast 、 slow 同步向前走，直到 fast.next 为 null

此时，fast 为最后一个节点，slow 就是倒数第 n+1 个节点，此时问题就变更为删除链表中的 slow 的后继节点

但存在一个问题，当链表长度为 n 时，fast 是前进不到 n+1 个节点位置的，所以此时有两种解决思路：

• 创建一个头节点 preHead ，设置 preHead.next = head ，这样就可以解决以上问题，删除倒数第 n 个节点后，返回的 preHead.next 即可
• 另外一种是，fast 快指针提前走 n 步后，判断 fast.next 是否为 null ，即 fast 是否是最后一个节点，如果是，则 head 为倒数第 n 个节点，此时问题可以简化为删除头节点;如果不是， fast = fast.next ，fast 再前进一步，slow 为倒数第 n+1 个节点，也解决了以上问题。

解决方案一：添加 preHead 节点

 
 
 

  
  
  
const removeNthFromEnd = function(head, n) { 
  
  
  
    let preHead = new ListNode(0) 
  
  
  
    preHead.next = head 
  
  
  
    let fast = preHead, slow = preHead 
  
  
  
    // 快先走 n+1 步 
  
  
  
    while(n--) { 
  
  
  
        fast = fast.next 
  
  
  
    } 
  
  
  
    // fast、slow 一起前进 
  
  
  
    while(fast && fast.next) { 
  
  
  
        fast = fast.next 
  
  
  
        slow = slow.next 
  
  
  
    } 
  
  
  
    slow.next = slow.next.next 
  
  
  
    return preHead.next 
  
  
  
}; 
 
 
 

解决方案二：单独处理倒数第 n 节点

 
 
 

  
  
  
const removeNthFromEnd = function(head, n) { 
  
  
  
    let fast = head, slow = head 
  
  
  
    // 快先走 n 步 
  
  
  
    while(--n) { 
  
  
  
        fast = fast.next 
  
  
  
    } 
  
  
  
    if(!fast.next) return head.next 
  
  
  
    fast = fast.next 
  
  
  
    // fast、slow 一起前进 
  
  
  
    while(fast && fast.next) { 
  
  
  
        fast = fast.next 
  
  
  
        slow = slow.next 
  
  
  
    } 
  
  
  
    slow.next = slow.next.next 
  
  
  
    return head 
  
  
  
}; 
 
 
 

时间复杂度：O(n)

空间复杂度：O(1)

来源：https://github.com/sisterAn/JavaScript-Algorithms

分享文章：每日：删除链表倒数第N个结点
文章URL：http://www.shufengxianlan.com/qtweb/news3/36053.html

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

广告

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