leeycode19.删除链表的倒数第N个节点 c++详解

题目

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。 示例： 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后，链表变为 1->2->3->5. 说明： 给定的 n 保证是有效的。 进阶： 你能尝试使用一趟扫描实现吗？

分析

题目要求删除链表倒数第n个节点，我们逆向思考，删除正向第L-n+1个节点，我们只用求得链表长度L就可以求得删除节点的前一个节点，然后将该节点指向下下个节点就能求解成功。

解决方案

我写了两种方法，方法二更加简洁一些，省去了单独考虑删除的节点为头节点的情况 方法一：逆向思维 执行用时 : 4 ms 内存消耗 : 8.4 MB

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode*temp=head; 
        ListNode*before=head;
        int L=0;//记录链表长度
        int m;
        while(temp)//计算链表长度
        {
            L++;
            temp=temp->next;
        }
        m=L-n-1;
        if(m<0)//m<0就是L=n,删除的是第一个节点
        {
            head=head->next;
            return head;
        }
        while(m>0)//删除的节点不是第一个节点，求的是删除节点的前一个节点before
        {
            m--;
            before=before->next;
        }
        before->next=before->next->next;
        return head;
    }
};

方法二：设置两个相隔为n的指针，first指针即为删除节点的前一个节点 执行用时 : 4 ms 内存消耗 : 8.6 MB

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode*res=new ListNode(0);//新建节点可以不用单独考虑头节点的问题
        res->next=head;
        ListNode*first=res;
        ListNode*second=res;
        for(int i=0;i<n+1;i++)
            second=second->next;
        while(second)
        {
            first=first->next;
            second=second->next;
        }
        first->next=first->next->next;
        return res->next;
    }
};