给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？
https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
示例1：
image输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例2：
输入：head = [1], n = 1
输出：[]
示例3：
输入：head = [1,2], n = 1
输出：[1]
提示：
链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
Java解法
思路：
- 面试被问的一道题，当时回答了转双链表、用栈处理，然而并没有接收到什么反馈。这次来试试顺便看看我差在哪里
- 栈解：头结点入栈，随后出栈，到第N个移除，继续出栈；简单，一把过，但效率不高
- 双链表：改变了数据结构，不太合理，弃用
- 双指针：两个指针在同一趟循环中遍历，前指针与后指针间隔为N，这样保证了前指针移到末尾时，后指针正好到要移除的位置的前一结点；效率很高，但不知道为啥耗内存了，还少用一个栈
package sj.shimmer.algorithm;
import java.util.Stack;
/**
* Created by SJ on 2021/2/5.
*/
class D12 {
public static void main(String[] args) {
System.out.println(removeNthFromEnd(ListNode.createNode(new int[]{1,2,3,4,5}),2));
System.out.println(removeNthFromEnd(ListNode.createNode(new int[]{1}),1));
System.out.println(removeNthFromEnd(ListNode.createNode(new int[]{1,2}),1));
}
public static ListNode removeNthFromEnd(ListNode head, int n) {
if (head == null) {
return head;
}
Stack<ListNode> stack = new Stack<>();
ListNode temp = head;
stack.push(temp);
while (temp.next != null) {
stack.push(temp.next);
temp = temp.next;
}
while (!stack.isEmpty()) {
if (n==1) {//n 是个数，从1开始
ListNode listNode = stack.pop();
if (stack.isEmpty()) {
return listNode.next;
}else {
ListNode pop = stack.pop();
pop.next = listNode.next;
return head;
}
}
stack.pop();
n--;
}
return head;
}
public static ListNode removeNthFromEnd2(ListNode head, int n) {
if (head == null) {
return head;
}
ListNode temp = head;
ListNode preRemove = null;
int i = 0;
while (temp.next != null) {
i++;
temp = temp.next;//前指针移动
if (i >=n) {//当等待间隔满足n时，后指针开始移动
if (preRemove == null) {
preRemove =head;
}else {
preRemove = preRemove.next;
}
}
}
if (preRemove == null) {//说明n超出或等于链表长度
if (head == null) {
return null;
}
return head.next;
}else {
preRemove.next = preRemove.next.next;
}
return head;
}
}
栈解
双指针
官方解
-
计算链表长度
两次遍历，一次算长度，一次移除结点
- 时间复杂度：O(L)，其中 L 是链表的长度。
- 空间复杂度：O(1)
-
栈
类似我的栈解
- 时间复杂度：O(L)
- 空间复杂度：O(L)。主要为栈的开销。
-
一次遍历
双指针解法，但官方解写的更优雅
class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0, head); ListNode first = head; ListNode second = dummy; for (int i = 0; i < n; ++i) { first = first.next; } while (first != null) { first = first.next; second = second.next; } second.next = second.next.next; ListNode ans = dummy.next; return ans; } }- 时间复杂度：O(L)
- 空间复杂度：O(1)。
