题解 | #调整牛群顺序#

调整牛群顺序

https://www.nowcoder.com/practice/a1f432134c31416b8b2957e66961b7d4

一、知识点:

链表、遍历、双指针

二、文字分析:

算法的实现思路如下:

  1. 创建一个虚拟的头结点preHead,使其指向链表的头结点head
  2. 初始化两个指针fastslow,将它们都指向preHead
  3. fast指针向后移动n个节点,即使其指向链表中的第n个节点。
  4. 同时将fastslow指针向后移动,直到fast指针指向链表的最后一个节点。
  5. 此时,slow指针所指的节点是链表中的倒数第n个节点。
  6. target节点指向slow.next,即倒数第n个节点。
  7. slow.next指向slow.next的下一个节点,即跳过倒数第n个节点。
  8. target.next置为null,将其作为新链表的尾节点。
  9. target节点插入到fast指针所指的位置,即链表的末尾。
  10. 返回更新后的链表头结点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;
    }
}

全部评论

相关推荐

1 收藏 评论
分享
牛客网
牛客企业服务