Leetcode 删除链表的倒数第N个节点

本文最后更新于:2020年11月19日 上午

地址:https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/6/linked-list/42/

题目

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

示例:

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

说明:

给定的 n 保证是有效的。

进阶:

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

我的解决方案

常规的方法会想到要计算出链表的长度L,然后再从头结点开始往后遍历L-n-1个结点,即倒数第n个结点的前一个结点,再删除要删除的倒数第n个结点(pre->next = pre->next->next;)。而题目要求用一趟扫描实现,所以需要用到两个指针precur都初始化为指向链表头结点,然后cur指针往后移n个结点到链表的第 n+1 个结点,再把 precur 同时往后移直到 curnext 指针指向 NULL ,即 cur 指向链表最后一个结点,此时 pre 指向倒数第 n 个结点的前一个结点,用同样的方法(pre->next = pre->next->next;)删除倒数第 n 个结点即可。

/**
 * 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 *root = head;   //作为返回值
        ListNode *pre = head;
        ListNode *cur = head;
        for (int i = 0; i < n; i++)   //*cur指向第n+1个结点
            cur = cur->next;
        if (cur == NULL)    //说明倒数第n的结点就是头结点
            root = head->next;    //将头指针改为指向第二个节点即可删除头结点
        else {
            while (cur->next != NULL)    //pre和cur同是往后移直到cur指向尾结点
            {
                pre = pre->next;
                cur = cur->next;
            }
            pre->next = pre->next->next;   //删除pre结点的后一个结点,即倒数第n个结点
        }
        return root;
    }
};

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!