美文网首页
Remove Nth Node From End of List

Remove Nth Node From End of List

作者: 极速魔法 | 来源:发表于2017-06-25 11:12 被阅读2次

    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) {
    
            if(head==NULL){
                return NULL;
            }
    
            ListNode* dummyHead=new ListNode(0);
            dummyHead->next=head;
            //p->target...->q(NULL)
            ListNode* p=dummyHead;
    
            ListNode* q=dummyHead;
            for(int i=0;i<n+1;i++){
                //ensure q !=NULL
                assert(q);
                q=q->next;
            } 
    
            //find node
            while(q != NULL){
                p=p->next;
                q=q->next;
            }
    
            //delete node
            ListNode* delNode=p->next;
            p->next=delNode->next;
            delete delNode;
    
            ListNode* ret=dummyHead->next;
            delete dummyHead;
            return ret;
        }
    };
    

    相关文章

      网友评论

          本文标题:Remove Nth Node From End of List

          本文链接:https://www.haomeiwen.com/subject/niglcxtx.html