题解 | #调整牛群顺序#
调整牛群顺序
https://www.nowcoder.com/practice/a1f432134c31416b8b2957e66961b7d4
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) { //链表长度<=1或者n=1直接返回原链表头节点 if (head == null || head.next == null || n == 1) { return head; } //初始化一个变量 listNodeLength为1,表示链表的长度 int listNodeLength=1; //创建一个指针end指向链表的头节点,遍历链表,记录链表长度 ListNode end=head; while(end.next !=null){ listNodeLength++; end=end.next; } //倒数第n个节点的位置 n=listNodeLength-n+1; //新建两个指针指向头结点 ListNode pre=head; ListNode cur=head; // 创建一个变量val,用于存储目标节点的值 int val=-1; // 遍历链表,每遍历一个节点,n减1 while(cur!=null){ n--; // 当n为0时,表示找到了倒数第n个节点 if(n==0){ //判断倒数第n个节点是否为头节点 if(cur == head){ // 如果是的话,将val设为头节点的值 val=head.val; head=head.next; }else{ // 将val设为该节点的值,并将pre的next指针指向cur的next指针,即删除该节点 val=cur.val; pre.next=cur.next; } break; } pre=cur; cur=cur.next; } //找到链表末尾,并将倒数第n个节点的值创建一个新的节点添加到末尾 end.next=new ListNode(val); return head; } }
本题考差知识点:链表的遍历删除操作。
本题使用java语言解答。
解题思路如下:
- 首先,判断链表的长度是否小于等于1,或者n是否为1,如果是的话,则不需要进行任何操作,直接返回原链表头节点。
- 初始化一个变量sz为1,表示链表的长度。创建一个指针end指向链表的头节点,通过遍历链表直到end指向链表的最后一个节点,同时记录链表的长度。
- 将n的值重新赋值为sz - n + 1,即倒数第n个节点在正数的位置。
- 创建两个指针pre和cur,初始化为链表的头节点。创建一个变量val,用于存储目标节点的值。
- 遍历链表,每遍历一个节点,n减1。当n为0时,表示找到了倒数第n个节点。
- 判断倒数第n个节点是否为头节点,如果是的话,将val设为头节点的值,并将头节点指向下一个节点。
- 如果倒数第n个节点不是头节点,将val设为该节点的值,并将pre的next指针指向cur的next指针,即删除该节点。
- 找到链表末尾,并将倒数第n个节点的值创建一个新的节点添加到末尾。
- 返回调整后的链表头节点。 这段代码的主要优点是:采用了一次遍历的方式找到倒数第n个节点的前一个节点,并且只需要对链表进行一次操作,具有较好的效率。但也要注意考虑特殊情况,如链表长度小于等于1或者n为1的情况。