题目
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.
解题之法
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
if (!head->next) return NULL;
ListNode *pre = head, *cur = head;
for (int i = 0; i < n; ++i) cur = cur->next;
if (!cur) return head->next;
while (cur->next) {
cur = cur->next;
pre = pre->next;
}
pre->next = pre->next->next;
return head;
}
};
分析
这道题让我们移除链表倒数第N个节点,限定n一定是有效的,即n不会大于链表中的元素总数。
还有题目要求我们一次遍历解决问题,那么就得想些比较巧妙的方法了。
我们首先要考虑的时,如何找到倒数第N个节点,由于只允许一次遍历,所以我们不能用一次完整的遍历来统计链表中元素的个数,而是遍历到对应位置就应该移除了。
那么我们需要用两个指针来帮助我们解题,pre和cur指针。
首先cur指针先向前走N步,如果此时cur指向空,说明N为链表的长度,则需要移除的为首元素,那么此时我们返回head->next即可。
如果cur存在,我们再继续往下走,此时pre指针也跟着走,直到cur为最后一个元素时停止,此时pre指向要移除元素的前一个元素,我们再修改指针跳过需要移除的元素即可。
网友评论