NC53 #删除链表的倒数第n个节点#
删除链表的倒数第n个节点
http://www.nowcoder.com/practice/f95dcdafbde44b22a6d741baf71653f6
先便利一遍查数,然后再走一遍删节点。
class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { int count = 0; ListNode *pHead = head; while(head != nullptr) { head = head->next; count++; } if(n == count) return pHead->next; ListNode *pre = nullptr, *now = pHead; for(int i = 1; i < count - n + 1; i++) { pre = now; now = now->next; } pre->next = now->next; return pHead; } };
也可以前后指针,前指针先走k步,然后两个指针一起往前走。
注意处理特殊情况。
class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode *dummy = new ListNode(0); dummy->next = head; ListNode *pHead = head, *slow = head, *fast = head, *pre = dummy; for(int i = 0; i < n; i++) fast = fast->next; while(fast != nullptr) { fast = fast->next; pre = slow; slow = slow->next; } pre->next = slow->next; if(pre == dummy) return dummy->next; else return pHead; } };