LeetCode - 删除链表的倒数第N个节点 - 一趟扫描 - 初级算法

还是 链表的问题有趣啊

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5. 说明：

给定的 n 保证是有效的。

进阶：

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

一趟扫描实现 ？删除倒数第n个节点
能吗
答案是可以的
不过 需要使用两个指针 两个以相同的速度移动的指针
但是呢 一个指向现在 一个指向未来
比如 例子里给出的 删除倒数第 2 个
我们初始化两个指针
如果 一个指针 指向 i 的话 另一个指针就指向 i + 2
当 指向 i + 2 的那个指针 指向了 null
不就意味着 指向 i 的那个指针 指向的 是倒数 第 2 个吗
就好像 是 一个指针 指向的现在 另一个指针 指向了未来
所以 你可以在现在 的时刻 知道未来发生的事情
神奇啊

上 代码 看看

 /**
 * 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) {
        ListNode* firstP = head;
        ListNode* nextP = head;
        int i;
        // 先循环 n 次 让 nextP 去到 n 天 的未来 看看情况
        for(i = 0;i < n;i ++){
            nextP = nextP -> next;
        }
        // 如果呢 n 天后 是 世界末日了 
        //那么 说明  这个链表 总共有 n 个 节点 
        //要删除 的 倒数第 n 个 节点 
        //不就是 第一个节点 那么接下来删除第一个就好了 
        //先看看 这个链表是否长度为1  
        //长度要是为 1 的话 删掉第一个 不就什么也没有了呀 直接 head = null 
        //否则 执行删除第一个节点
        if(nextP == NULL){
            if(head -> next == NULL)
                head = NULL;
            else{
                head -> val = head->next->val;
                head -> next = head -> next ->next;
            }
            return head;
        }
        // nextP  和 firstP 以相同的速度向未来进发
        while(nextP -> next != NULL){
            nextP = nextP -> next;
            firstP = firstP -> next;
        }
        // nextP 走到了 世界末日 firstP 执行删除操作
        firstP -> next = firstP -> next-> next;

        return head;
    }
};

总的来说 也是不难的啦
不过 要注意的是 一种特殊情况
链表 总共长 n 要删除 倒数 第 n 个
相当于 删除 第一个
但是呢 head 节点 就是指向的第一个
如何删除 自己呢 ？
就要用到上一个问题的思路了 详情可以看我上一篇文章哦