美文网首页
[Leetcode] 50. Remove Nth Node F

[Leetcode] 50. Remove Nth Node F

作者: 时光杂货店 | 来源:发表于2017-03-20 21:37 被阅读6次

    题目

    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指向要移除元素的前一个元素,我们再修改指针跳过需要移除的元素即可。

    相关文章

      网友评论

          本文标题:[Leetcode] 50. Remove Nth Node F

          本文链接:https://www.haomeiwen.com/subject/dwginttx.html