[LeetCode 19] Remove Nth Node From End of List

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.

Diffculty
Medium

Similar Problems

Analysis

注意： 由于list只有next节点，所以删除时我们的指针p应该在前一个Node停下来， 否则就没法把前一个Node的next指向本Node的next了

可以先弄个假的头结点，这样就可以统一处理prev结点的问题了 class Solution { public: ListNode removeNthFromEnd(ListNode head, int n) { ListNode readHead(-1); readHead.next = head; head = &readHead; ListNode *cur = head; while(n-- > 0) cur = cur->next; while(cur->next != nullptr){ cur = cur->next; head = head->next; } delete head->next; head->next = head->next->next; return readHead.next; } };

class Solution { public: ListNode removeNthFromEnd(ListNode head, int n) { if(head == nullptr || n < 1) return head; ListNode* cur = head; while(cur != nullptr) { --n; cur = cur->next; } if(n == 0) head = head->next; // 倒数第K个节点就是头结点 if(n < 0){ cur = head; while(++n != 0) cur = cur->next; cur->next = cur->next->next; // 此时移动到的节点就是要删除的节点的前节点 } return head;

}

};