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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode* removeNthFromEnd(ListNode* head, int n) { if( head == NULL ) return NULL; ListNode * p1 = head, *p2 = head, *p3 = head; while(n != 0 && p3 != NULL){ p3 = p3->next; n--; } if( n != 0) return head; while(p3 != NULL){ p1 = p2; p2 = p2->next; p3 = p3->next; } if(p1 != p2){//正常删除 p1 -> next = p2->next; } else{//说明删除的是head节点，边界条件2 head = p2->next; } delete p2; return head; }}; |
19. Remove Nth Node From End of List
原文：http://www.cnblogs.com/zhxshseu/p/e48e968a984cb12d2ec8e764a775774f.html