题目的主要信息:

  • 给定一个链表,要删除链表倒数第n个节点,并返回链表的头
  • 题目保证链表长度一定大于等于nn

方法一:长度统计法

具体做法:

既然要删掉倒数第n个元素,那肯定得先找到这个元素,试想一下,如果是数组我们怎么找这个元素的?肯定是先统计数组长度LL,然后根据LnL-n得到下标,再根据下标访问。但是很可惜,链表无法直接统计长度,也无法根据下标,我们能做的就是遍历链表。既然如此,那就两次遍历,第一次统计长度,第二次找到倒数第n个位置。

  • step 1:给链表添加一个表头,处理删掉第一个元素时比较方便。
  • step 2:遍历整个链表,统计链表长度。
  • step 3:准备两个指针,一个指向原始链表头,表示当前节点,一个指向我们添加的表头,表示前序节点。两个指针同步遍历LnL-n次找到倒数第nn个位置。
  • step 4:前序指针的next指向当前节点的next,代表越过当前节点连接,即删去该节点。
  • step 5:返回去掉添加的表头。
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int length = 0; //记录链表长度
        ListNode* res = new ListNode(-1); //添加表头
        res->next = head;
        ListNode* cur = head; //当前节点
        ListNode* pre = res; //前序节点
        while(cur != NULL){ //找到链表长度
            length++;
            cur = cur->next;
        }
        cur = head; //回到头部
        for(int i = 0; i < length - n; i++){ //从头遍历找到倒数第n个位置
            pre = cur;
            cur = cur->next;
        }
        pre->next = cur->next; //删去倒数第n个节点
        return res->next; //返回去掉头节点
    }
};

复杂度分析:

  • 时间复杂度:O(n)O(n),其中nn为链表长度,最坏情况遍历整个链表2次
  • 空间复杂度:O(1)O(1),常数级指针,无额外辅助空间使用

方法二:双指针

具体做法:

我们无法逆序遍历链表,就很难得到链表的倒数第nn个元素,那我们可以试试反过来考虑,如果当前我们处于倒数第nn的位置上,即距离链表尾的距离是nn,那我们假设双指针指向这两个位置,二者同步向前移动,当前面个指针到了链表头的时候,两个指针之间的距离还是nn。虽然我们没有办法让指针逆向移动,但是我们刚刚这个思路却可以正向实施:

  • step 1:给链表添加一个表头,处理删掉第一个元素时比较方便。
  • step 2:准备一个快指针,在链表上先走nn步。
  • step 3:准备慢指针指向原始链表头,代表当前元素,前序节点指向添加的表头,这样两个指针之间相距就是一直都是nn
  • step 4:快慢指针同步移动,当快指针到达链表尾部的时候,慢指针正好到了倒数nn个元素的位置。

具体过程可以参考下列图示:

alt

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* res = new ListNode(-1); //添加表头
        res->next = head;
        ListNode* cur = head; //当前节点
        ListNode* pre = res; //前序节点
        ListNode* fast = head;
        while(n--) //快指针先行n步
            fast = fast->next;
        while(fast != NULL){ //快慢指针同步,快指针到达末尾,慢指针就到了倒数第n个位置
            fast = fast->next;
            pre = cur;
            cur = cur->next;
        }
        pre->next = cur->next; //删除该位置的节点
        return res->next; //返回去掉头
    }
};

复杂度分析:

  • 时间复杂度:O(n)O(n),其中nn为链表长度,最坏情况遍历整个链表1次
  • 空间复杂度:O(1)O(1),常数级指针,无额外辅助空间使用