[0019] 删除链表的倒数第N个节点

• GitHub
• http://leetcode.xuezhisd.top/post/b85f80d1.html
• https://leetcode.com/problems/remove-nth-node-from-end-of-list
• https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list

题目描述

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

示例：

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


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

说明：

给定的 n 保证是有效的。

进阶：

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

Related Topics

链表

双指针

题目解析

• 本题是一道模拟题

不确定性

方法一：两次遍历法

分析

• 首先将链表的长度求出，根据n计算出需要指针移动的节点数
• 利用循环将指针移到被删除节点的前一个节点
• 删除倒数的第n个节点

思路

• 在链表最前端，建立一个哑结点
• 使用指针p遍历链表，得到链表的长度len，并根据len-n求得需要移动的距离
• 从头开始遍历链表，将指针移到倒数n+1号节点的位置上
• 删除倒数的第n个节点

注意

• 当链表只有一个节点且n=1时，p->next = p->next->next 的右值无法取到，因此添加哑结点

知识点

• 链表的遍历

复杂度

• 时间复杂度 O(n)
• 空间复杂度 O(1)

代码

ListNode* removeNthFromEnd(ListNode* head, int n) {
	ListNode* dummy = new ListNode(0);
	dummy->next = head;
	ListNode* p = head;
	int len = 0;
	while (p){
		len++;
		p = p->next;
	}
	int tmplen = len - n;
	p = dummy;
	while (tmplen){
		tmplen--;
		p = p->next;
	}
	p->next = p->next->next;
	return dummy->next;
}

方法二：一次遍历法

分析

• 建立两个指针，一个指针先向链表末端移动n个节点
• 两个指针同时向链表末端移动，直到前一个指针移动到最后一个节点处
• 后一个指针所在的位置，即是要删除倒数第n个节点的位置

思路

• 在链表最前端，建立一个哑结点
• 建立两个指针p和q，分别指向哑结点
• 让q指针向向链表末端移动n个节点
• 两个指针同时向链表末端移动，直到q指针移动到最后一个节点处
• 删除倒数的第n个节点

注意

• 当链表只有一个节点且n=1时，p->next = p->next->next 的右值无法取到，因此添加哑结点

知识点

• 双指针同时遍历

复杂度

• 时间复杂度 O(n)
• 空间复杂度 O(1)

代码

ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* p = dummy;
        ListNode* q = dummy;

        while (n--){
            q = q->next;
        }
        while (q->next){
            p = p->next;
            q = q->next;
        }
        p->next = p->next->next;
        return dummy->next;
    }

相关题目

• https://leetcode-cn.com/problems/rotate-list/