ARTICLE DETAIL

建站实战干货

来自一线的建站与推广经验沉淀,每一条都经过真实交付验证。

力扣25题: K 个一组翻转链表

2026/9/29 19:10:34 拓冰建站 浏览量
力扣25题: K 个一组翻转链表

【题目链接】力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台,解题代码如下:

class Solution {public ListNode reverseKGroup(ListNode head, int k) {ListNode curNode = head;ListNode groupHead, groupTail = head, lastGroupTail = null;int len = 0;while (curNode != null) {curNode = curNode.next;if (++len % k == 0) {groupHead = reverseGroup(groupTail, curNode);if (lastGroupTail != null) {lastGroupTail.next = groupHead;lastGroupTail = groupTail;} else {lastGroupTail = head;head = groupHead;}groupTail = curNode;}}lastGroupTail.next = groupTail;return head;}private ListNode reverseGroup(ListNode head, ListNode tail) {ListNode curNode = head, lastNode = null, nextNode;while (curNode != tail) {nextNode = curNode.next;curNode.next = lastNode;lastNode = curNode;curNode = nextNode;}return lastNode;}

【解题步骤】:

  1. 记录几个指针:curNode当前节点,用于依次遍历所有节点;lastGroupTail :上一K组的尾指针;groupHead:当前K组首指针,翻转之前是尾指针;groupTail:当前K组尾指针,翻转之前是首指针
    ListNode curNode = head;
    ListNode groupHead, groupTail = head, lastGroupTail = null;
  2. 依次遍历链表,每K个节点一组进行相应处理,对于当前K个节点来说,就是简单的链表翻转操作;
    curNode = curNode.next;
    if (++len % k == 0) {groupHead = ListNode.reverseList(groupTail, curNode);。。。
  3. 新翻转一个K组指针后,如果上一K组节点不为空:将上一K组的尾指针指向当前K组首指针,然后再将当前K组尾指针设置为上一K组的尾指针
    if (lastGroupTail != null) {lastGroupTail.next = groupHead;lastGroupTail = groupTail;
    } 
  4. 如果上一K组节点为空,说明处理的是第一组,那么翻转之后的链表首节点就是第一组的尾节点,上一K组尾指针设置为之前的链表首节点:
    else {lastGroupTail = head;head = groupHead;
    }
  5. 设置当前组的尾指针为当前节点
    groupTail = curNode;
  6. 重复2,3步操作,,直至遍历到链表结尾
  7. 最后收一下尾:将当前K组尾指针指向最后还未翻转的一组(不足K个节点)的首指针
    lastGroupTail.next = groupTail;

【思路总结】

1)首先要对复杂问题分解:再复杂的问题像“”庖丁解牛“”一样,找到其中脉络,进行分解之后,都会被切割成简单的个体小单元,很容易理解和掌握。

2)其次要学会“”依此类推“”的思路:算法的解决大数据的问题,基本都是找出其中规律,周而复始的进行重复性操作,直至结束:

3)最后处理一下开头、结尾或者空指针等特殊情况即可