题目链接:
https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
题目:
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
解析:
快指针start;慢指针end;
此题目需要删除一个节点,并且返回新的链表,使用快慢指针法,先移动快指针n个身位,(两个指针相差n-1个节点),再将两个指针一起移动,当快指针的next为null时,证明已经移动到链表末端,并指向最后一个节点,此时慢指针的下一个节点就是要删除的节点,直接将现在指向的节点end.next=end.next.next;跳过此节点以此达到删除目的;
注:return 应该返回pre.next;并非head,当头节点为空时,会出现问题;
点击查看代码
/**
* 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 pre =new ListNode(0);
pre.next=head;
//使用双指针
ListNode satrt=pre;ListNode end=pre;
//将快指针移动n个身位
while(n!=0){
satrt=satrt.next;
n--;
}
//同时移动,直到链表末端
while(satrt.next!=null){
end=end.next;
satrt=satrt.next;
}
//因为快指针现在指向末端节点,中间有n-1个节点,加起来才是n个节点,所以,需要删除的是end的下一个节点;
end.next=end.next.next;
return pre.next;
}
}