题目考察的知识点:链表、双指针。
题目解答方法的文字分析:这道题目给定了一个链表,表示农场里一群牛,每头牛都有一个编号,编号由一个整数表示,整数范围是[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;
}
}

京公网安备 11010502036488号