题解 | #牛群的重新分组#java
牛群的重新分组
https://www.nowcoder.com/practice/267c0deb9a6a41e4bdeb1b2addc64c93
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 k int整型 * @return ListNode类 */ public ListNode reverseKGroup (ListNode head, int k) { // write code here ListNode dummy = new ListNode(-1); dummy.next = head; ListNode prev = dummy; ListNode curr = head; int count = 0; while (curr != null) { count++; if (count % k == 0) { // 获取下一个组的起始节点 ListNode nextGroupStart = curr.next; // 将当前组的末尾节点指向 null,便于后续反转操作 curr.next = null; // 反转当前组内的节点 ListNode reversedGroupStart = reverseList(prev.next); ListNode reversedGroupEnd = prev.next; // 将反转后的组内节点与下一个组连接起来 reversedGroupEnd.next = nextGroupStart; prev.next = reversedGroupStart; // 更新 prev 和 curr 指针到下一个组的起始位置 prev = reversedGroupEnd; curr = nextGroupStart; } else { curr = curr.next; } } return dummy.next; } /** * 反转链表 * * @param head 链表的头节点 * @return 反转后的链表的头节点 */ private ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while (curr != null) { ListNode nextTemp = curr.next; curr.next = prev; prev = curr; curr = nextTemp; } return prev; } }
我们首先定义了链表节点的类 ListNode
。然后创建了一个方法 reverseKGroup
,用于反转链表的前 k 个节点。
在 reverseKGroup
方法中,我们创建了一个哑节点 dummy
,将其指向链表的头节点。然后使用两个指针 prev
和 curr
分别指向每个组的起始和当前节点。
通过循环遍历链表,当遍历到满足每 k 个节点一组的位置时,进行以下操作:
- 获取下一个组的起始节点
nextGroupStart
。 - 将当前组的末尾节点指向 null,便于后续的反转操作。
- 调用
reverseList
方法反转当前组内的节点,得到反转后的起始节点reversedGroupStart
和末尾节点reversedGroupEnd
。 - 将反转后的组内节点与下一个组连接起来。
- 更新
prev
和curr
指针到下一个组的起始位置。
在 reverseList
方法中,我们使用三个指针 prev
、curr
和 nextTemp
,分别表示当前节点、当前节点的前一个节点和当前节点的后一个节点。通过循环遍历链表,将节点的 next
指针指向前一个节点,实现反转操作。
最后,返回哑节点 dummy
的下一个节点,即为修改后的牛群链表的头节点。
该题知识点包括链表的基本操作,包括反转链表和处理链表指定位置的元素。