一、题目

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

示例:

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

**说明:**给定的 n 保证是有效的。

**进阶:**你能尝试使用一趟扫描实现吗?


二、解决方法

方法一:两次遍历算法

思路: 注意到这个问题可以容易地简化成另一个问题:删除从列表开头数起的第 (Ln+1)(L - n + 1) 个结点,其中 LL 是列表的长度。只要我们找到列表的长度 LL,这个问题就很容易解决。
算法: 首先我们添加一个哑结点作为辅助结点,该结点位于列表头部。哑结点用来简化某些极端情况,例如列表中只含有一个结点,或需要删除列表的头部。在第一次遍历中,我们找出列表的长度 LL。然后设置一个指向哑结点的指针,并移动它遍历列表,直至它到达第 (Ln)(L - n) 个结点那里。我们把第 (Ln)(L - n) 个结点的 next 指针重新链接至第 (Ln+2)(L - n + 2) 个结点,完成这个算法。变化过程如下图所示:

代码如下(通过)

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) 
{
    struct ListNode* dummy = head;
    struct ListNode* first = head;
    int length = 1;    
    while (first->next != NULL) // calculate the length of the linked list
    {
        length++;
        first = first->next;
    }
    if (n == length)
        return head->next;
    int index = length - n - 1;
    while (index > 0)
    {
        index--;
        dummy = dummy->next;
    }
    dummy->next = dummy->next->next;
    return head;
}

复杂度分析

  • 时间复杂度:O(L)O(L),该算法对列表进行了两次遍历,首先计算了列表的长度 LL ,其次找到第 (Ln)(L - n) 个结点。 操作执行了 2Ln2L-n 步,时间复杂度为 O(L)O(L)
  • 空间复杂度:O(1)O(1),我们只用了常量级的额外空间。

方法二:一次遍历算法

思路:可以设想假设设定了双指针 p 和 q 的话,当 q 指向末尾的 NULL,p 与 q 之间相隔的元素个数为 n 时,那么删除掉 p 的下一个指针就完成了要求。

  • 设置虚拟节点 dummyHead 指向 head
  • 设定双指针 p 和 q,初始都指向虚拟节点 dummyHead
  • 移动 q,直到 p 与 q 之间相隔的元素个数为 n
  • 同时移动 p 与 q,直到 q 指向的为 NULL
  • 将 p 的下一个节点指向下下个节点

动画描述如下图所示:

代码实现(accepted):

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) 
{
    struct ListNode* dummyHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummyHead->next = head;

    struct ListNode* p = dummyHead;
    struct ListNode* q = dummyHead;
    for (int i = 0; i < n + 1; i++)
    {
        q = q->next;
    }
    while (q)
    {
        p = p->next;
        q = q->next;
    }

    struct ListNode* delNode = p->next;
    p->next = delNode->next;
    free(delNode);

    struct ListNode* retNode = dummyHead->next;
    free(dummyHead);

    return retNode;
}

复杂度分析:

  • 时间复杂度:O(L)O(L),该算法对含有 LL 个结点的列表进行了一次遍历。因此时间复杂度为 O(L)O(L)
  • 空间复杂度:O(1)O(1),我们只用了常量级的额外空间。