Tag Archives: 快慢指针

LeetCode Remove Nth Node From End of List

19. Remove Nth Node From End of List

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Follow up:

Could you do this in one pass?


给定一个链表,要求删除倒数第n个元素。我想到的做法是遍历一遍链表,同时把链表每个元素保存到一个数组中,遍历完之后就知道链表长度,这样就可以计算出倒数第n个元素是哪个元素,然后直接删掉即可。 代码如下:

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n)
    {
        if (head->next == NULL)
            return NULL;
        vector<ListNode*> nodes;
        ListNode* ln = head;
        while (ln) {
            nodes.push_back(ln);
            ln = ln->next;
        }
        int target = nodes.size() – n;
        if (target == 0) {
            head->next = NULL;
            head = nodes[target + 1];
        }
        else if (target == nodes.size() – 1) {
            nodes[target – 1]->next = NULL;
        }
        else {
            nodes[target – 1]->next = nodes[target + 1];
        }
        return head;
    }
};

本代码提交AC,用时8MS。一看排名倒数,肯定还有更高效的算法,因为这种解法需要保存链表,而且是用vector.push_back的,所以肯定耗时。看题解,原来这是典型的快慢指针题,我这个非ACMer还是反应迟钝呀。

我们维护一个快指针和慢指针,初始的时候快慢都在起点,然后快指针先跑n步,此时快慢指针的距离为n,然后快慢指针同时跑,这样就能保持距离为n,当快指针到达末尾(NULL)的时候,慢指针刚好是在倒数第n的位置,真是巧妙。
但是为了删除倒数第n个节点,需要知道其前一个节点,所以让快指针到达NULL的前面位置停,即faster->next==NULL的时候停下来。
完整代码如下:

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n)
    {
        if (head == NULL || head->next == NULL)
            return NULL;
        ListNode *slower = head, *faster = head;
        while (n–) {
            faster = faster->next;
        }
        if (faster == NULL)
            return head->next;
        while (faster->next) {
            faster = faster->next;
            slower = slower->next;
        }
        slower->next = slower->next->next;
        return head;
    }
};

本代码提交AC,用时4MS,果然快了不少。