题目:leetcode19. 删除链表的倒数第 N 个结点
描述:
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
思路:
让前面的节点比后面的节点先走n+1步,因为从链表的尾节点的下一个节点开始,倒数n个节点就是要删除的节点,删除一个节点我们需要找到这个节点的前一个节点,我们需要找到倒数n+1节点,所以我们先让前面的节点先从虚拟头结点先走n+1步,再让前面的节点和后面的节点一起走,当前面的节点走到尾节点的下一个节点的时候,后面的节点也走到了要删除的节点的前一个节点,我们就可以删除了。
class ListNode {public int val;public ListNode next;public ListNode(){};public ListNode(int val){ this.val=val;}public ListNode(int val, ListNode next) {this.val = val;this.next = next;}
}public class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {if(n==0)return head;ListNode drum=new ListNode(-1);drum.next=head;ListNode cur=drum;ListNode pre=drum;for (int i=0;i<n+1;i++)cur=cur.next;while(cur!=null){cur=cur.next;pre=pre.next;}pre.next=pre.next.next;return drum.next;}
}