一、知识点:
链表、遍历、双指针
二、文字分析:
算法的实现思路如下:
- 创建一个虚拟的头结点
preHead
,使其指向链表的头结点head
。 - 初始化两个指针
fast
和slow
,将它们都指向preHead
。 - 将
fast
指针向后移动n个节点,即使其指向链表中的第n个节点。 - 同时将
fast
和slow
指针向后移动,直到fast
指针指向链表的最后一个节点。 - 此时,
slow
指针所指的节点是链表中的倒数第n个节点。 - 将
target
节点指向slow.next
,即倒数第n个节点。 - 将
slow.next
指向slow.next
的下一个节点,即跳过倒数第n个节点。 - 将
target.next
置为null,将其作为新链表的尾节点。 - 将
target
节点插入到fast
指针所指的位置,即链表的末尾。 - 返回更新后的链表头结点
preHead.next
。
使用了双指针技巧,只需要遍历链表一次就可以完成节点的移动操作,因此时间复杂度为O(n),其中n是链表的长度。空间复杂度为O(1),只需要使用固定数量的额外指针来完成操作。
三、编程语言:
java
四、正确代码:
import java.util.*; // public class ListNode { // int val; // ListNode next = null; // public ListNode(int val) { // this.val = val; // } // } public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @param n int整型 * @return ListNode类 */ public ListNode moveNthToEnd(ListNode head, int n) { if (n == 1) { return head; } ListNode preHead = new ListNode(-1); preHead.next = head; ListNode fast = preHead; ListNode slow = preHead; // 将fast指针移动到链表的第n个节点 for (int i = 0; i < n; i++) { fast = fast.next; } // 同时移动fast和slow指针,直到fast指针达到链表末尾 while (fast.next != null) { fast = fast.next; slow = slow.next; } ListNode target = slow.next; slow.next = slow.next.next; target.next = null; fast.next = target; return preHead.next; } }