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

2024-01-01 10:25:36

【题目链接】力扣(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个节点来说,就是简单的链表翻转操作;
    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)最后处理一下开头、结尾或者空指针等特殊情况即可

文章来源:https://blog.csdn.net/IT_Fly/article/details/135322258
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。