解题思路:
链表题目:哑节点、栈、快慢指针(双指针)
方法一:计算链表长度
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dum = new ListNode(0, head);
int len = getLen(head);
ListNode cur = dum;
for (int i = 0; i < len - n; i++) {
cur = cur.next;
}
cur.next = cur.next.next;
return dum.next;
}
public int getLen(ListNode head) {
int len = 0;
while (head != null) {
head = head.next;
len++;
}
return len;
}
}
方法二:栈
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dum = new ListNode(0, head);
Deque<ListNode> stack = new LinkedList<>();
ListNode cur=dum;
while(cur!=null){
stack.push(cur);
cur=cur.next;
}
for(int i=0;i<n;i++){
stack.pop();
}
ListNode pre=stack.peek();
pre.next=pre.next.next;
return dum.next;
}
}
方法三:快慢指针(双指针)
注意fast从head开始,而不是dum
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dum = new ListNode(0, head);
ListNode fast=head;
ListNode slow=dum;
for(int i=0;i<n;i++){
fast=fast.next;
}
while(fast!=null){
slow=slow.next;
fast=fast.next;
}
slow.next=slow.next.next;
return dum.next;
}
}