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

题目来源

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

题目描述

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

示例

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

题目解析

本题可以使用 “双指针” 来解题。

定义一个快指针 fast，一个慢指针 slow，初始时都指向 head；

然后，让 fast 指针先走 n 步；

之后，让 slow、fast 指针同时走，直到 fast == null，此时 slow 指针指向的就是链表的倒数第 n 个节点。

fast 先走 n 步，然后 slow、fast 才同时走，则 slow 和 fast 将会一直保持 n 步的差距，那么当 fast 越界时（即 fast == null 时），slow 就处于倒数第 n 个节点。

比如示例1：

但是本题的链表是单向链表，即当前节点只能通过next找到下一个节点，而无法找到上一个。

因此，我们想要删除倒数第 n 个节点，则需要找到倒数第 n+1 个节点，按照前面slow、fast指针逻辑，则当fast走到倒数第1个节点时，slow位于倒数第n+1个节点位置

以示例1为例：

找到倒数第 n+1 个节点后，删除倒数第 n 个节点的操作为：

slow.next = slow.next.next

当链表为单节点链表时，上面slow、fast指针运动会存在问题，比如示例2：

为了避免上面问题，我们可以为输入链表，添加一个虚拟头节点 dummy_head

C源码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode* dummy_head = (struct ListNode*)malloc(sizeof(struct ListNode)); // 定义一个虚拟头节点（更好处理单节点链表）
    
    dummy_head->val = 0;
    dummy_head->next = head;

    struct ListNode* fast = dummy_head;
    struct ListNode* slow = dummy_head;

    for (int i = 0; i < n; i++) { // 先让 fast 指针走 n 步，目的是为了让 fast 和 slow 之间差 n 步
        fast = fast->next;
    }

    while (fast->next != NULL) { // 然后 fast、slow 指针同时走，当fast走到倒数第 1 个节点时，slow 此时处于倒数第 n + 1 个节点，因为 fast 和 slow 之间差 n 步
        fast = fast->next;
        slow = slow->next;
    }

    slow->next = slow->next->next; // 删除倒数第n个节点，其中slow是倒数第n+1个节点

    return dummy_head->next;
}

C++源码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy_head = new ListNode(0, head); // 定义一个虚拟头节点（更好处理单节点链表）

        ListNode* fast = dummy_head;
        ListNode* slow = dummy_head;

        for (int i = 0; i < n; i++) { // 先让 fast 指针走 n 步，目的是为了让 fast 和 slow 之间差 n 步
            fast = fast->next;
        }

        while (fast->next != nullptr) { // 然后 fast、slow 指针同时走，当fast走到倒数第 1 个节点时，slow 此时处于倒数第 n + 1 个节点，因为 fast 和 slow 之间差 n 步
            fast = fast->next;
            slow = slow->next;
        }

        slow->next = slow->next->next; // 删除倒数第n个节点，其中slow是倒数第n+1个节点

        return dummy_head->next;
    }
};

Java源码实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy_head = new ListNode(0, head); // 定义一个虚拟头节点（更好处理单节点链表）

        ListNode fast = dummy_head;
        ListNode slow = dummy_head;

        for (int i = 0; i < n; i++) { // 先让 fast 指针走 n 步，目的是为了让 fast 和 slow 之间差 n 步
            fast = fast.next;
        }

        while (fast.next != null) { // 然后 fast、slow 指针同时走，当fast走到倒数第 1 个节点时，slow 此时处于倒数第 n + 1 个节点，因为 fast 和 slow 之间差 n 步
            fast = fast.next;
            slow = slow.next;
        }

        slow.next = slow.next.next; // 删除倒数第n个节点，其中slow是倒数第n+1个节点

        return dummy_head.next;
    }
}

Python源码实现

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: Optional[ListNode]
        :type n: int
        :rtype: Optional[ListNode]
        """
        dummy_head = ListNode(0, head)

        fast = dummy_head
        slow = dummy_head

        for i in range(n):
            fast = fast.next
        
        while fast.next:
            fast = fast.next
            slow = slow.next
        
        slow.next = slow.next.next

        return dummy_head.next
        

JavaScript源码实现

// Definition for singly-linked list.
// function ListNode(val, next) {
//   this.val = (val === undefined ? 0 : val)
//   this.next = (next === undefined ? null : next)
// }

// function toList(nums) {
//   const head = new ListNode(nums[0]);

//   let node = head;
//   for (let i = 1; i < nums.length; i++) {
//     node.next = new ListNode(nums[i]);
//     node = node.next;
//   }

//   return head;
// }



/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function (head, n) {
  const dummy_head = new ListNode(0, head); // 定义一个虚拟头节点（更好处理单节点链表）

  let fast = dummy_head;
  let slow = dummy_head;

  for (let i = 0; i < n; i++) { // 先让 fast 指针走 n 步，目的是为了让 fast 和 slow 之间差 n 步
    fast = fast.next;
  }

  while (fast.next != null) { // 然后 fast、slow 指针同时走，当fast走到倒数第 1 个节点时，slow 此时处于倒数第 n + 1 个节点，因为 fast 和 slow 之间差 n 步
    fast = fast.next;
    slow = slow.next;
  }

  slow.next = slow.next.next; // 删除倒数第n个节点，其中slow是倒数第n+1个节点

  return dummy_head.next;
};

// removeNthFromEnd(toList([1]), 1);