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.
每次遇到这种链表相关的题的时候我都习惯新建一个Guard作为头,这样可以简化很多判断。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ #define LN ListNode class Solution { public: ListNode *removeNthFromEnd(ListNode *head, int n) { // Start typing your C/C++ solution below // DO NOT write int main() function LN* Guard=new LN(-1); Guard->next=head; LN* ans; LN* pre=Guard; LN* pDel=head; LN* pFast=head; if (n<=0) ans=head; while(pFast&&n--) pFast=pFast->next; if (n>0) ans=head; else { while(pFast) { pFast=pFast->next; pre=pre->next; pDel=pDel->next; } pre->next=pDel->next; delete pDel; pDel=0; ans=Guard->next; } delete Guard; Guard=0; return ans; } };