problem:

Given a linked list, remove the n^th 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.

 

 Solution:解决方式采用双指针，前后指针相差n

1 /** 2  * Definition for singly-linked list. 3  * struct ListNode { 4  *     int val; 5  *     ListNode *next; 6  *     ListNode(int x) : val(x), next(NULL) {} 7  * }; 8  */ 9 class Solution {10 public:11     ListNode* removeNthFromEnd(ListNode* head, int n) {12     //题意是要删除从最后一个节点往前数的第n个节点 考虑到只有一个节点时没有办法删除 加一个dummy13     14     ListNode *dummy=new ListNode(-1);15     dummy->next=head;16     ListNode *pre=dummy;17     ListNode *last=dummy;18     19     //找到last的初始位置20     while(n--)21     {22         last=last->next;   23     }24     25     while(last->next!=NULL)26     {27         pre=pre->next;28         last=last->next;29     }30     //删除节点 32     ListNode *object=pre->next;33     pre->next=pre->next->next;34     delete object;35     36     return dummy->next;37     38     }39 };