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