题解 | #牛群分隔#
牛群分隔
https://www.nowcoder.com/practice/16d9dc3de2104fcaa52679ea796e638e
该题考察的知识点包括:
单链表的遍历和操作:需要对链表进行遍历,根据节点的值将节点连接到两个不同的链表中。 虚拟节点的使用:通过创建虚拟节点来简化代码,避免对头节点进行特殊处理。 指针的移动:通过移动指针来连接节点,并在遍历过程中更新指针的位置。 边界条件处理:需要考虑链表为空的情况。
代码解释:
检查特殊情况:如果链表为空或n小于等于1,则直接返回原链表头节点。 使用快慢指针的思想,初始化两个指针slow和fast,它们都指向链表的头节点。 快指针fast先移动n个节点。如果快指针已经到达链表的末尾,说明需要移动的是头节点,直接返回原链表头节点的下一个节点。 当快指针fast没有到达链表末尾时,快慢指针同时移动,直到快指针到达链表末尾。此时,慢指针slow指向倒数第n+1个节点,也就是需要移动的倒数第n个节点的前一个节点。 将倒数第n个节点从链表中剥离出来,并将slow.next指向剩余部分的起始节点。 根据是否移动了头节点,返回原链表的头节点或新的头节点。
编程语言: Java
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param head ListNode类
* @param x int整型
* @return ListNode类
*/
public ListNode cow_partition (ListNode head, int x) {
// write code here
// 创建一个虚拟节点,用于存放小于x的节点
ListNode lessNode = new ListNode(0);
// 创建一个虚拟节点,用于存放大于等于x的节点
ListNode greaterNode = new ListNode(0);
// 指向小于x节点的指针
ListNode lessPtr = lessNode;
// 指向大于等于x节点的指针
ListNode greaterPtr = greaterNode;
while (head != null) {
if (head.val < x) {
lessPtr.next = head; // 将节点连接到lessNode后面
lessPtr = lessPtr.next; // 移动指针
} else {
greaterPtr.next = head; // 将节点连接到greaterNode后面
greaterPtr = greaterPtr.next; // 移动指针
}
head = head.next; // 遍历链表
}
greaterPtr.next =
null; // 将大于等于x的节点的next指针置为null,断开与后面的节点的连接
lessPtr.next =
greaterNode.next; // 将小于x的节点的next指针指向大于等于x的节点,完成分隔
return lessNode.next; // 返回分隔后的链表头节点
}
}