如何通过一次遍历删除链表倒数第N个元素

给定一个链表，删除链表的倒数第n个节点，并且返回链表的头结点。本篇经验将分享一个快慢指针算法，在O(1)的空间复杂度下返回结果。声明链表节点类首先，我们需要声明一个链表节点类，用于构建链表结构。```

给定一个链表，删除链表的倒数第n个节点，并且返回链表的头结点。本篇经验将分享一个快慢指针算法，在O(1)的空间复杂度下返回结果。

声明链表节点类

首先，我们需要声明一个链表节点类，用于构建链表结构。

```java

public class ListNode {

int val;

ListNode next;

ListNode(int x) { val x; }

}

```

通过快慢指针找到倒数第n个元素

我们可以通过两个间隔为n的节点指针，找到倒数第n个元素。

首先，初始化两个指针，分别指向链表的头部。然后，将快指针向前移动n步。接着，快指针和慢指针一起向前移动，直到快指针遍历完链表。此时，慢指针会指向倒数第n个节点元素。需要注意的是，如果快指针向前移动n步之后已经为空，则说明我们要删除的是第一个元素。

```java

public ListNode removeNthFromEnd(ListNode head, int n) {

ListNode dummy new ListNode(0);

head;

ListNode fast dummy;

ListNode slow dummy;

// 快指针先向前移动n步

for (int i 0; i < n; i ) {

fast ;

}

// 快慢指针一起向前移动，直到快指针遍历完链表

while (fast ! null) {

fast ;

slow ;

}

// 删除倒数第n个节点

;

return ;

}

```

输出链表

为了验证算法的正确性，我们可以编写代码输出整个链表。

```java

public void printList(ListNode head) {

ListNode curNode head;

while (curNode ! null) {

( " ");

curNode ;

}

();

}

```

测试代码

在主方法中，我们可以构建一个链表并调用上述方法删除倒数第n个元素，并将结果输出到控制台。

```java

public static void main(String[] args) {

Solution solution new Solution();

ListNode head new ListNode(1);

ListNode node2 new ListNode(2);

ListNode node3 new ListNode(3);

ListNode node4 new ListNode(4);

ListNode node5 new ListNode(5);

node2;

node3;

node4;

node5;

int n 2;

ListNode result (head, n);

(result);

}

```

运行结果

运行主方法，观察控制台输出，可以验证算法的正确性。

```

1 2 3 5

```

提交算法

最后，我们可以将算法提交到面试平台进行测试。