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.
Note:
Given n will always be valid.
Try to do this in one pass.

C++:
01 ListNode *removeNthFromEnd(ListNode *head, int n) {
02         if(head==NULL)
03             return NULL;
04         ListNode* prv=head;
05         ListNode* test=head;
06         for(int i=0;i<n;i++)
07             test=test->next;
08         if(test==NULL){
09             ListNode* tmp=head->next;
10             delete head;
11             return tmp;
12         }
13         while(test->next!=NULL){
14             prv=prv->next;
15             test=test->next;
16         }
17         ListNode* tmp=prv->next;
18         prv->next=tmp->next;
19         delete tmp;
20         return head;
21 }
Advertisements
This entry was posted in Array and linked list. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s