分享程序员开发的那些事...
更新时间：2021-09-23 00:12:08
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.
主要难点是通过一趟遍历寻找链表倒数第k个元素，具体见代码注释 本文地址
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步，然后快慢指针一起走，块指针指向尾节点时，慢指针指向倒数第n个节点 13 ListNode* fast = head, *slow = head, *slowpre = NULL; 14 for(int i = 1; i < n; i++)fast = fast->next; 15 while(fast->next) 16 { 17 fast = fast->next; 18 slowpre = slow; 19 slow = slow->next; 20 } 21 if(slow == head) 22 head = head->next; 23 else 24 slowpre->next = slow->next; 25 delete slow; 26 return head; 27 } 28 };