一、前言
盲目刷题只会让自己心态爆炸，所以本期14天算法学习计划，也是LeetCode上的 [算法]学习计划，在本专栏的每一篇文章都会整理每一天的题目并给出详细题解，以及知识点的整理
二、知识点
链表
链表——初识链表
快慢指针
一种双指针的特殊移动方式，一般快指针的移动步长为慢指针的两倍，通过两个指针之间的差来解决问题
三、LeetCode19. 删除链表的倒数第 N 个结点
1.题目
LeetCode19. 删除链表的倒数第 N个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1
输出：[]
示例 3：
输入：head = [1,2], n = 1
输出：[1]
2.解题思路（含图）
本题我们可以用快慢指针的思路去解决，即利用两个指针差解决问题
要删除的元素最终为慢指针指向的元素的下一个节点（链表特有的，下文会提到），而当慢指针指的下一个节点向要删除的元素时，快指针的下一个节点恰好指向null（终止条件）
这时候肯定有人问：这快慢指针的差怎么设定？
题目给了我们一个值n用来表示要删除的元素是倒数第几个，按照上面的思想，我们来列举一下
当n=1时： slow.next指向最后一个元素，slow指向倒数第二个元素，fast.next指向null，fast指向最后一个元素，差值为0
当n=2时： slow.next指向倒数第二个元素，slow指向倒数第三个元素，fast.next指向null，fast指向最后一个元素，差值为1
当n=3时： slow.next指向倒数第三个元素，slow指向倒数第四个元素，fast.next指向null，fast指向最后一个元素，差值为2
…
注：此处的差值指的是快慢指针指向元素之间间隔的元素个数，如[1,2,3,4,5]数组，慢指针指向1，快指针指向3，那么差值为1
从上面的枚举可以看出，快慢指针差值为 n-1 ，所以要让快指针先移动n步才能保证差值为n-1
当快指针移动了n步以后，让快慢指针同时移动，直到快指针指向元素的下一个节点为NULL为止
在链表中，index.next指向的是地址值，让index.next = indext.next.next的话，跳过了下一个元素的地址值，变相的就删除了下一个元素（index指向元素的下一个），这也是上文中说到的链表特性
3.代码实现
/** * 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 slow = head, fast = head; //让快指针先移动n，产生快慢指针的差为n-1 for(int i = 0; i < n; i++ ){ fast = fast.next; } //当元素为1时，返回值为空 if(fast == null){ return head.next; } //快慢指针同时移动，直至快指针指向元素下一个节点为空 while(fast.next != null){ fast = fast.next; slow = slow.next; } //删除元素 slow.next = slow.next.next; //返回值 return head; } }
4.复杂度分析
- 时间复杂度：O(L)
其中 L 是链表的长度
- 空间复杂度：O(1)
5.验证代码
6.其它方法（来自力扣）
1️⃣计算链表长度
class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0, head); int length = getLength(head); ListNode cur = dummy; for (int i = 1; i < length - n + 1; ++i) { cur = cur.next; } cur.next = cur.next.next; ListNode ans = dummy.next; return ans; } public int getLength(ListNode head) { int length = 0; while (head != null) { ++length; head = head.next; } return length; } }
- 时间复杂度：O(L)
其中 L 是链表的长度
- 空间复杂度：O(1)
2️⃣栈
class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0, head); Deque<ListNode> stack = new LinkedList<ListNode>(); ListNode cur = dummy; while (cur != null) { stack.push(cur); cur = cur.next; } for (int i = 0; i < n; ++i) { stack.pop(); } ListNode prev = stack.peek(); prev.next = prev.next.next; ListNode ans = dummy.next; return ans; } }
- 时间复杂度：O(L)
其中 L 是链表的长度
- 空间复杂度：O(L)
其中 L 是链表的长度，主要为栈的开销
四、结语
本题的快慢指针与前面的题目不太一样，要善于利用链表的特性解决问题，优化代码
