离线下载
PDF版 ePub版

柯于旺 · 更新于 2018-11-28 11:00:43

Remove Nth Node From End of List(从列表尾部删除第 N 个结点)

翻译

给定一个链表,移除从尾部起的第 n 个结点,并且返回它的头结点。

例如,给定链表:1->2->3->4->5,n = 2。

在移除尾部起第二个结点后,链表将变成:1->2->3->5。

备注:

给定的 n 是有效的,代码尽量一次通过。

原文

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.

Note:
Given n will always be valid.
Try to do this in one pass.

代码

class Solution{
public:
    ListNode* removeNthFromEnd(ListNode* head, int n){
        ListNode newHead(0);
        newHead.next = head;
        count = n;
        return solution1(&newHead);
    }
private:
    int count;
    ListNode* solution1(ListNode* newHead){
        subSol1(newHead);
        return newHead->next;
    }
    bool subSol1(ListNode* node){
        if(!node) return false;
        if(subSol1(node->next)) return true;
        if(count--) return false;
        ListNode *tmp = node->next;
        node->next = tmp->next;
        delete tmp;
        return true;
    }
};