Skip to content

LeetCode 19. 删除链表的倒数第 N 个节点

作者:Choi Yang
更新于:6 个月前
字数统计:317 字
阅读时长:1 分钟
阅读量:

题目描述

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

示例:

cpp
给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后,链表变为 1->2->3->5.

说明:

给定的 n 保证是有效的。

进阶:

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

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

双指针,先让一个指针 q 走 n 步,然后另一个指针 p 一起走,当第一个指针 q 走到尾的时候,此时 p 指针就指向了我们要删除的节点,进行删除即可。

javascript
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function (head, n) {
  let dummyHead = new ListNode();
  dummyHead.next = head;
  let p = dummyHead;
  let q = dummyHead;
  let k = n;
  while (k--) q = q.next; // 先让一个指针先走n步
  while (q.next) {
    // 一起走
    q = q.next;
    p = p.next;
  }
  p.next = p.next.next; // 找到删除节点,进行删除
  return dummyHead.next;
};
javascript
学如逆水行舟,不进则退

Contributors

Choi Yang