题解 | #牛群的重新分组#
牛群的重新分组
https://www.nowcoder.com/practice/267c0deb9a6a41e4bdeb1b2addc64c93
题目考察的知识点:
- 链表数据结构的理解和应用:题目中牛群被用单链表表示,对链表节点的操作是解决问题的关键。
- 链表节点的翻转:题目要求每 k 个节点一组进行翻转,这需要对链表的节点进行翻转操作。
- 链表的遍历和指针操作:遍历链表,并在需要的地方进行指针操作来实现节点的翻转和链表的拼接。
- 条件判断和循环:需要判断节点数量是否满足每 k 个节点一组的条件,以及使用循环来遍历链表和处理每组节点的翻转。
题目解答方法的文字分析:本题要求对给定的单链表进行每 k 个节点一组的翻转操作。首先,我们需要定义一个翻转链表的函数 reverseLinkedList
,用于将链表中的一部分(k 个节点)进行翻转。然后,我们使用循环遍历链表,每次取 k 个节点进行翻转,并将翻转后的链表拼接到结果链表中。在翻转的过程中,我们使用指针操作来实现节点的翻转和链表的拼接。如果节点数量不足 k 个,剩余的节点将保持原有顺序,不进行翻转。最后,返回 dummy 节点的下一个节点作为翻转后的链表头节点。
本题解析所用的编程语言:本题解析使用的编程语言是 Java。
完整且正确的编程代码(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 k int整型 * @return ListNode类 */ public ListNode reverseKGroup (ListNode head, int k) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode prevGroupTail = dummy; ListNode curr = head; while (true) { int count = 0; ListNode kthNode = curr; while (count < k && kthNode != null) { kthNode = kthNode.next; count++; } if (count == k) { ListNode nextGroupHead = kthNode; ListNode newHead = reverseLinkedList(curr, kthNode); prevGroupTail.next = newHead; prevGroupTail = curr; prevGroupTail.next = nextGroupHead; curr = nextGroupHead; } else { break; } } return dummy.next; } private ListNode reverseLinkedList(ListNode head, ListNode tail) { ListNode prev = null; ListNode curr = head; while (curr != tail) { ListNode nextNode = curr.next; curr.next = prev; prev = curr; curr = nextNode; } return prev; } }