LeetCode 19 Remove Nth Node From End of List

标签: 链表问题 LeetCode 发布于:2022-02-05 16:57:47 编辑于:2022-02-05 17:25:46 浏览量:400

题目分析

https://leetcode.com/problems/remove-nth-node-from-end-of-list/

直接法

首先遍历一遍得到总长度,第二次遍历的时候就知道所在的节点的序号了。

快慢指针

虽说这道题挺简单的,但是不小心的话还是有可能没办法 one pass:

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode dummy(0, head);
        ListNode* l = &dummy;
        ListNode* r = &dummy;
        for (int i = 1; i <= n; i++) {
            r = r->next;
        }
        while (r && r->next) {
            r = r->next;
            l = l->next;
        }
        if (l->next) {
            l->next = l->next->next;
        } else {
            l->next = nullptr;
        }
        return dummy.next;
    }
};

之前做这道题时的实现,更加干净:

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *fast = head, *slow = head;
        for (int i = 0; i < n; ++i) {
            fast = fast->next;
        }
        if (!fast) return head->next;
        while (fast->next) {
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;
        return head;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/