力扣hot100 删除链表的倒数第 N 个结点 快慢指针 递归回溯

Problem: 19. 删除链表的倒数第 N 个结点

思路

👩?🏫 参考题解

💖 递归

? 时间复杂度: $O(n)$
🌎 空间复杂度: $O(n)$

class Solution {
//	递归
	int cnt = 0;//计数器

	public ListNode removeNthFromEnd(ListNode head, int n)
	{
		if (head == null)
			return head;
		head.next = removeNthFromEnd(head.next, n);
		cnt++;//回溯时计数
		if (cnt == n)//倒数第n个节点
			return head.next;//把它的next返回
		return head;
	}
}

💖 双指针

? 时间复杂度: $O(n)$
🌎 空间复杂度: $O(1)$

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
	public ListNode removeNthFromEnd(ListNode head, int n)
	{
		ListNode dummy = new ListNode(0, head);//哑兵节点，用于删除头结点
		ListNode first = head;//先行指针
		for (int i = 0; i < n; i++)
			first = first.next;
		ListNode cur = dummy;//先行指针和 cur 指针始终保持 n 的距离
		while (first != null)// first 一直移动到尾节点
		{
            // 双指针一起移动
			first = first.next;
			cur = cur.next;
		}
		cur.next = cur.next.next;//cur后面的就是要删除的节点
		return dummy.next;
	}
}