LeetCode 19.Remove Nth Node From End of List (删除链表的倒数第N个节点)

我不是女神ヾ 2022-05-11 00:38 110阅读 0赞

题目描述:  
给定一个链表，删除链表的倒数第 *n* 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.
    
    当删除了倒数第二个节点后，链表变为 1->2->3->5.

**说明：**

给定的 *n* 保证是有效的。

**进阶：**

你能尝试使用一趟扫描实现吗？

Accepted C++ Solution:

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode* removeNthFromEnd(ListNode* head, int n) {
            if (!head)
                return nullptr;
            
            ListNode new_head(-1);
            new_head.next = head;
            
            ListNode *slow = &new_head, *fast = &new_head;
            
            for (int i = 0; i < n; i++)
                fast = fast->next;
            
            while (fast->next) {
                fast = fast->next;
                slow = slow->next;
            }
            
            ListNode *to_be_deleted = slow->next;
            slow->next = slow->next->next;
            
            delete to_be_deleted;
            
            return new_head.next;
            
        }
    };

用两个指针进行扫描，前后两个指针之间间隔为n，当前指针到达链表末，则后面指针指向倒数第n+1个。

优化：

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode* removeNthFromEnd(ListNode* head, int n) {
            if (!head)
                return nullptr;
            
            ListNode **slow = &head, *fast = head;
            
            for (int i = 1; i < n; i++)
                fast = fast->next;
            
            while (fast->next) {
                fast = fast->next;
                slow = &((*slow)->next);
            }
            
            *slow = (*slow)->next;
            
            return head;
            
        }
    };