26
2017
09

19. Remove Nth Node From End of List。

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

For 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.


给定一个链表和数字n,要删除掉倒数第n个元素。最开始使用了stack,先遍历一遍原先的链表,然后依次放入栈中,再遍历栈并且使用头插法将栈中的元素一次组合起来,但是此刻需要对n做自减,当n等于0的时候就说明需要删除这个节点。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(!head) {
            return NULL;
        }

        stack<ListNode*> nodes;
        ListNode* result = new ListNode(0);

        while(head) {
            nodes.push(head);
            head = head->next;
        }

        while(!nodes.empty()) {
            n--;
            if(!n) {
                nodes.pop();
                if(nodes.empty()) break;
            }

            nodes.top()->next = result->next;
            result->next = nodes.top();
            nodes.pop();
        }
        return result->next;
    }
};

使用这一种方法可以达到这个级别。

这里写图片描述


第二种方法就是使用两个指针,然后用其中一个(first)先行遍历,遍历n各节点。然后两个指针(first和second)再同时遍历,遍历的终止条件就是第一个(first)指针到达尾部。那这样的话因为first最开始已经遍历了n步了,所以当first到达尾部的时候,second正好还差n步到达尾部,所以此刻就找到了所需要删除的地方。就好比两个人走一百步,第一个人先走了10步,然后两个人再同时走90步,这时候第一个人已经走了100步,而第二个走了90步,正好是差10步走完。利用这个原理,然后在调整其中的一些细节,比如说为了防止空指针的出现可以使用一个自己制造的头结点。

#include <iostream>
#include <stack>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {


        if(!head) {
            return NULL;
        }

        ListNode* result = new ListNode(0);
        result->next = head;
        ListNode* first = result;
        ListNode* second = result;

        n++;
        while(n) {
            n--;
            first = first->next;
        }

        while(first) {//直到first走到了尾部,那么first下一个就是我们需要删除的节点
            first = first->next;
            second = second->next;
        }

        second->next = second->next->next;//删除一个节日

        return result->next;


        /*if(!head) {
            return NULL;
        }

        stack<ListNode*> nodes;
        ListNode* result = new ListNode(0);

        while(head) {
            nodes.push(head);
            head = head->next;
        }

        while(!nodes.empty()) {
            n--;
            if(!n) {
                nodes.pop();
                if(nodes.empty()) break;
            }

            nodes.top()->next = result->next;
            result->next = nodes.top();
            nodes.pop();
        }
        return result->next;*/
    }
};

int main() {
    Solution s;


    ListNode node1(1);
    ListNode node2(2);
    ListNode node3(3);
    ListNode node4(4);
    ListNode node5(5);

    node1.next = &node2;
    node2.next = &node3;
    node3.next = &node4;
    node4.next = &node5;

    ListNode* p = s.removeNthFromEnd(&node1,2);

    while(p) {
        cout << p->val;
        cout << endl;
        p = p->next;
    }

}

参考资料:https://leetcode.com/articles/remove-nth-node-end-list/


按理说这个比第一种方法快一点,因为第一种遍历了两次,这个只遍历了一次,但是运行结果一样。

这里写图片描述

上一篇:failed to chmod no such file or directory 下一篇:Android Architecture Component系列