题目考察的知识点:链表、双指针。
题目解答方法的文字分析:这道题目给定了一个链表,表示农场里一群牛,每头牛都有一个编号,编号由一个整数表示,整数范围是[0, 100]。我们需要将链表中的倒数第n个结点移到链表的末尾,并返回调整后的链表的头结点。
为了解决这个问题,我们可以使用双指针的方法。首先,我们引入一个dummy
节点,它的作用是方便处理链表的头节点。然后,我们定义两个指针fast
和slow
,同时将它们指向dummy
节点。我们先将fast
指针向前移动n步,以找到倒数第n个结点的位置。
接下来,我们同时移动fast
和slow
指针,直到fast
指针到达链表的末尾。此时,slow
指针就指向了倒数第n个结点的前一个结点。我们通过这个方法可以将倒数第n个结点移到链表末尾。
具体步骤如下:
- 初始化
dummy
节点,将fast
和slow
指针都指向dummy
节点。 - 将
fast
指针向前移动n步,找到倒数第n个结点的位置。 - 同时移动
fast
和slow
指针,直到fast
指针到达链表的末尾,slow
指针就指向了倒数第n个结点的前一个结点。 - 将倒数第n个结点移到链表末尾,即将其从链表中删除,并添加到链表的末尾。
最后,我们返回调整后的链表的头结点,即dummy.next
。
本题解析所用的编程语言: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 (head == null || n <= 1) { return head; } ListNode dummy = new ListNode(0); dummy.next = head; ListNode fast = dummy; ListNode slow = dummy; // 将fast指针向前移动n步 for (int i = 0; i < n; i++) { if (fast == null) { return head; // 链表长度小于n,直接返回原链表 } fast = fast.next; } // 同时移动fast和slow指针,直到fast到达链表末尾 while (fast != null && fast.next != null) { fast = fast.next; slow = slow.next; } // 将倒数第n个结点移到链表末尾 ListNode nthNode = slow.next; slow.next = slow.next.next; nthNode.next = null; // 将倒数第n个结点添加到链表末尾 ListNode curr = dummy; while (curr.next != null) { curr = curr.next; } curr.next = nthNode; return dummy.next; } }