题目描述

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

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

提示：

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

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

解题思路

暴力解：
链表的基本操作，因为是倒序，先数一遍链表长度。
快慢双指针：
image.png
快指针先走n步
image.png
随后慢指针开始走
image.png
当快指针走到末尾的时候，慢指针所指下一个节点就是要删除的节点
image.png

实现代码

  1. class ListNode {
  2.   int val;
  3.   ListNode next;
  4.   ListNode() {
  5.   }
  7.   ListNode(int val) {
  8.     this.val = val;
  9.     this.next = null;
  10.   }
  11.   ListNode(int val, ListNode next) {
  12.     this.val = val;
  13.     this.next = next;
  14.   }
  15. }
public ListNode removeNthFromEnd(ListNode head, int n) {
    // 判空
    if(head == null) {
      return null;
    }
    // 先获得长度
    int len = 0;
    for (ListNode cur = head; cur != null; cur = cur.next) {
      len++;
    }
    // 特殊处理，要删除的就是头节点的情况
    if(len-n == 0){
      head = head.next;
      return head;
    }
    // 正常删除
    ListNode pre = head;
    for (int i = 0; i <len - n - 1; i++) {
      pre = pre.next;
    }
    pre.next = pre.next.next;
    return head;
  }

public ListNode fastRemoveNthFromEnd(ListNode head, int n) {
    if(head == null) {
        return null;
    }
    ListNode fast = head;
    ListNode slow = head;
    // 快指针先走n步
    for (int i = 0; i < n; i++) {
        fast = fast.next;
    }
    // 刚好删除头节点
    if(fast == null){
        head = head.next;
        return head;
    }
    // 快慢指针同时走
    while(fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
    return head;
}

时间及空间复杂度分析

两种方法时间复杂度均为O(n)，空间复杂度O(1)
在leetcode的测试用例中，没体现出明显差异。当然，还是快慢指针更优。
image.png