Leetcode19-删除链表的倒数第N个结点

题目：删除链表的倒数第N个结点

解答：

方法一：快慢指针

ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode dummy(0);
        dummy.next = head;
        ListNode* fast = &dummy;
        ListNode* slow = &dummy;
        for(int i=0;i<n;i++)
        {
            if(fast!=nullptr){
                fast = fast->next;
            }else{
                return nullptr;//链表长度小于n
            }
        }
        while(fast->next!=nullptr)
        {
            slow = slow->next;
            fast = fast->next;
        }
        slow->next = slow->next->next;
        return dummy.next;
    }

时间复杂度：n；空间复杂度：1

8ms；79%

优化：利用“指针的指针”——思维逐渐向这种方法靠拢

ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode** t1 = &head;
        ListNode* t2 = head;
        for(int i=1;i<n;++i)
        {
            t2 = t2->next;
        }
        while(t2->next != nullptr)
        {
            t1 = &((*t1)->next);
            t2 = t2->next;
        }
        *t1 = (*t1)->next;//指针的指针删除结点的方法
        return head;
    }

4ms;100%