题目传送门
方法一:计算链表长度(迭代)
1.计算链表长度,并且定义哑节点链接链表。
2.从哑节点开始前进length-n次。即为被删除节点的前置节点。
3.进行删除操作。
4.返回哑节点的后置节点
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
//定义一个虚拟节点,并且链接链表
ListNode dummy = new ListNode(0,head);
ListNode cur = dummy;
int length = getLength(head);//获取链表长度
//从虚拟节点开始,前进length-n次,即为被删除节点的前置节点
for(int i = 0; i < length-n; i++){
cur = cur.next;
}
cur.next = cur.next.next;
return dummy.next;
}
public int getLength(ListNode head){
int length = 0;
while(head != null){
length++;
head = head.next;
}
return length;
}
}
方法二:栈
在 Java 中,虽然有
Stack
类,但推荐使用Deque
(例如LinkedList
或ArrayDeque
)来实现栈的功能。主要原因有:1. 设计上的问题
2. 性能优势
3. 双端队列的灵活性
4. 现代化的 API
1.定义一个虚拟节点,用来找到结果链表的头结点。
2.将链表节点全部入栈,包括虚拟节点。
3.出n次栈。也就是刚好把要删除节点出栈。
4.记录栈顶元素的地址。也就是被删除节点的前置节点。
5.链接链表。将前置节点与后置节点链接起来。
6.返回虚拟节点的下一个节点。
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;
}
}
标签:---,head,ListNode,cur,next,链表,节点,倒数第
From: https://blog.csdn.net/m0_73456341/article/details/143377214