删除链表中倒数第n个节点
给定一个链表,删除链表中倒数第n个节点,返回链表的头节点。
注意事项
链表中的节点个数大于等于n
样例
给出链表1->2->3->4->5->null和 n = 2.
删除倒数第二个节点之后,这个链表将变成1->2->3->5->null.
1 /** 2 * Definition of ListNode 3 * class ListNode { 4 * public: 5 * int val; 6 * ListNode *next; 7 * ListNode(int val) { 8 * this->val = val; 9 * this->next = NULL; 10 * } 11 * } 12 */ 13 14 15 class Solution { 16 public: 17 /* 18 * @param head: The first node of linked list. 19 * @param n: An integer 20 * @return: The head of linked list. 21 */ 22 ListNode * removeNthFromEnd(ListNode * head, int n) { 23 // write your code here 24 if (head == NULL || n < 1) return NULL; 25 ListNode *first = head; 26 ListNode *second = head; 27 ListNode *pre; 28 while (n) { 29 first = first->next; 30 n--; 31 } 32 while (first) { 33 first = first->next; 34 pre = second; //标记倒数第n个节点的前一个节点 35 second = second->next; 36 } 37 if (second == head) { 38 head = head->next; 39 } else { 40 pre->next = pre->next->next; 41 } 42 43 return head; 44 } 45 };