MENU

LeetCode19. Remove Nth Node From End of List(链表 / 模拟)

2019 年 03 月 05 日 • 阅读: 889 • LeetCode阅读设置

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;
    }
};
最后编辑于: 2022 年 03 月 25 日