网站建设公司简介范文律师免费咨询

LeetCode 19. 删除链表的倒数第N个结点

题目描述

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

思路

思路：快慢指针，快指针先移动n步，快慢指针再同时移动直到快指针到达链表末尾，此时慢指针指向的位置就是链表的倒数第n个结点的前面一个，移除next即可

/*** 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 dummyHead = new ListNode();dummyHead.next = head;ListNode fast = dummyHead, slow = dummyHead;// 快指针先移动n步int count = 0;while (count < n){count++;fast = fast.next;}// 快慢指针同时移动，直到快指针指向了最后一个节点，可以使用慢指针进行删除while (fast.next != null){fast = fast.next;slow = slow.next;}slow.next = slow.next.next;return dummyHead.next;}
}