凌云的博客

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

分类：algorithm| 发布时间：2016-07-04 23:24:00

---

题目

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

示例：

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

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

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

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

解法 1

一种直观的解法是先统计链表的大小，然后算出要删除的倒数 n 个节点的位置，然后删除。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int size = 0;
        for (ListNode *tmp = head; tmp; tmp = tmp->next) {
            ++size;
        }

        if (size == n) {
            ListNode *tmp = head;
            head = head->next;
            delete tmp;
            return head;
        }

        int offset = size - n - 1;
        ListNode *tmp = head;
        for (; offset; --offset, tmp = tmp->next) ;
        ListNode *toDelete = tmp->next;
        tmp->next = toDelete->next;
        delete toDelete;
        return head;
    }
};

算法 2

上述解法的问题在于需要多次遍历链表，不符合进阶的要求，可以通过两个指针来使得只需要遍历一次就可以达到目地。

主要思想是添加一个 dummy 节点，指向 head 节点，然后使用两个指针 (pre 和 post)，post 指针先从 dummy 开始往后移 n 步， 然后 pre 和 post 指针同时往后移，直到 post 指针为链表的末尾，此时 pre 的 next 指针正好是要删除的节点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode dump(0);
        dump.next = head;
        ListNode *pre = &dump, *post = &dump;
        while (n--) {
            post = post->next;
        }

        while (post->next) {
            post = post->next;
            pre = pre->next;
        }

        ListNode *toDelete = pre->next;
        pre->next = toDelete->next;
        delete toDelete;
        return dump.next;
    }
};