LeetCode19. Remove Nth Node From End of List（链表 / 模拟）

LeetCode19. Remove Nth Node From End of List（链表 / 模拟）

• Medium
• Accepted：356,264
• Submissions：1,047,909

Given a linked list, remove the n-th node from the end of list and return its head.

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.

Follow up:

Could you do this in one pass?

链接

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

题意

给定一个链表，删除它的倒数第n个结点。

题解

由于链表的特性，删除正数的某个结点比较简单，所以关键就在于我们如何将倒数第n个结点转换为正数某个结点。

我们可以设立两个指针p和q并构建一个虚拟头结点，让p指向虚拟头结点，让q指向第n+1个结点，然后一起后移，当q指向null的时候，p刚好指向要删除的结点的前一个结点，然后删除操作就很容易了。

当然，我们也可以先遍历一下整个链表，得到链表的长度l，然后将倒数第n个结点转化为正数第l-n+1个结点。

（吐槽一下，实际上后移应该是往前移，不过我这么说习惯了）

代码

• Runtime: 8 ms, faster than 100.00% of C++ online submissions for Remove Nth Node From End of List.
• Memory Usage: 9.8 MB, less than 11.70% of C++ online submissions for Remove Nth Node From End of List.

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* virtualHead = new ListNode(0);
        virtualHead->next = head;
        ListNode* p = virtualHead;
        ListNode* q = virtualHead;

        for (int i = 0; i < n + 1; ++i) // 后移
            q = q->next;
        while (q)
        {
            p = p->next;
            q = q->next;
        }

        ListNode* delNode = p->next; // 真删除结点
        p->next = delNode->next;
        delete delNode;
        
        ListNode* retNode = virtualHead->next; // 删除
        delete virtualHead;
        
        return retNode;
    }
};

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyNode = new ListNode(-1);
        dummyNode->next = head;
        
        ListNode* low = dummyNode;
        ListNode* fast = dummyNode;
        
        for (int i = 0; i < n; ++i)
            fast = fast->next;
        // 这里为了让 low 指向要删除节点的上一个节点，再往后走一步
        fast = fast->next;
        
        while (fast != NULL)
        {
            fast = fast->next;
            low = low->next;
        }
        
        ListNode* deleteNode = low->next;
        low->next = deleteNode->next;
        delete deleteNode;
        
        head = dummyNode->next;
        delete dummyNode;
        return head;
    }
};