题解 | #链表中的节点每k个一组翻转#

链表中的节点每k个一组翻转

https://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <cstddef>
class Solution {
 public:
  /**
   * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
   *
   *
   * @param head ListNode类
   * @param k int整型
   * @return ListNode类
   */

  pair<ListNode*, ListNode*> reversePart(ListNode* headNode, ListNode* tailNode) {
    ListNode* pre = new ListNode(-1);
    ListNode* cur = headNode;
    while (cur != tailNode) {
      ListNode* tmp = cur->next; //记录后面一个人
      cur->next = pre; //将当前人向后转
      pre = cur; // 更新前面一个人
      cur = tmp; // 更新当前人
    }
    cur->next = pre;
    return {cur, headNode};
  }
  ListNode* reverseKGroup(ListNode* head, int k) {
    // write code here
    if (head == NULL) {
      return nullptr;
    }
    ListNode* preInvNode = new ListNode(-2);
    preInvNode->next = head;
    ListNode* pre  = preInvNode;// 左边一棵树
    pre->next = head;
    ListNode* cur = pre;
    while (pre->next != NULL) {
      //寻找下一段链表的末端节点
      for (int i = 0; cur != NULL && i < k; i++) {
        cur = cur->next;
      }
      //如果链表的长度超过k, 则cur为第k个节点,否则cur = NULL.
      if (cur == nullptr) {
        return preInvNode->next;
      }
      //否则记录一下cur的下一个节点
      ListNode* cur_next  = cur->next;
      auto revheadtail = reversePart(pre->next, cur);
      pre->next = revheadtail.first;
      pre = revheadtail.second;
      pre->next = cur_next;
      cur = pre;
    }
    return preInvNode->next;
  }
};

思路是:遍历链表,每一次只翻转一段长为k的子链表。

只提交了两次就成功了,看来我确实是掌握了k个一组翻转链表的精髓,这是我通过努力记住了这个方法,为自己感到自豪。

全部评论

相关推荐

12-02 17:22
已编辑
西安交通大学 Java
华为 昇腾 ai软件开发 薪资20k x (14-16),职级13A,5%公积金,c/cpp
BLOOMING7:闭眼滴滴,华子给的又少又累
点赞 评论 收藏
分享
研一开学九月份速成的Java,项目是苍穹外卖和黑马点评,算法基础不好,八股文较为熟练,想找份小厂日常实习,希望牛友们给点意见,蟹蟹啦
求offer的花生米很聪敏:三个月学了这么多?spring springmvc mybatis springboot jvm juc,还做完了两个项目,还熟悉八股,会点算法。卧槽,我该反思了。我暑假开始的,就做了外卖,spring springmvc boot 那些原理好多都忘了,还在刷 jvm 视频,八股和算法也没开始
点赞 评论 收藏
分享
牛客533433175号:更可气的是我做完这些给我拒了
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务