一、知识点:
链表、遍历、双指针
二、文字分析:
算法的实现思路如下:
- 创建一个虚拟的头结点
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;
}
}

京公网安备 11010502036488号