题解 | #调整牛群顺序#
调整牛群顺序
https://www.nowcoder.com/practice/a1f432134c31416b8b2957e66961b7d4
此题需要考虑的边界条件较多，
我们采用双指针法，和虚拟头结点
设置变量表示是否第一步结束cur就是尾结点
一开始 pre和cur都指向虚拟头结点
第一步 cur向后跳n次，此时如果cur如果是尾结点，则flag为true
第二步 cur和pre一起向后跳，直到cur的后面就是null停
此时pre指向的是目标操作节点的前一个节点， cur指向尾结点。
首先判断目标操作节点 即pre.next是不是尾结点，是的话就不用操作了，直接返回head
不是就继续操作
最后返回时根据flag判断操作节点是否是头结点来决定返回啥。
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
public ListNode moveNthToEnd (ListNode head, int n) {
ListNode pre = new ListNode(-1);
pre.next = head;
ListNode cur = pre;
while (n-- > 0) {
cur = cur.next;
}
boolean flag = false;
if (cur.next == null) flag = true;
while (cur.next != null) {
pre = pre.next;
cur = cur.next;
}
// 此时pre在操作节点的前面，cur是尾结点。
// 操作开始
ListNode tmp = pre.next;
//如果该节点已经是尾结点，就不用再操作
if (tmp.next == null)return head;
pre.next = tmp.next;
cur.next = tmp;
tmp.next = null;
// 根据flag值返回节点
if (flag) return pre.next;
return head;
}
}
算法题刷刷刷 文章被收录于专栏
数组、链表、栈、队列、堆、树、图等。 查找和排序：二分查找、线性查找、快速排序、归并排序、堆排序等。 动态规划：背包问题、最长公共子序列、最短路径 贪心算法：活动选择、霍夫曼编码 图：深度优先搜索、广度优先搜索、拓扑排序、最短路径算法（如 Dijkstra、Floyd-Warshall） 字符串操作：KMP 算法、正则表达式匹配 回溯算法：八皇后问题、0-1 背包问题 分治算法：归并排序、快速排序
SHEIN希音公司福利 363人发布