题解 | #链表中的节点每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-01 12:34
已编辑
广东工业大学 Java
如题,fw🐭🐭,加上准备的太晚,大三上已找不到日常实习,导致连锁反应,下学期的暑期实习找不到好的实习,导致秋招找不到中大厂,现在是中小厂Java还有考公的选择,由于有些中小厂工作强度比肩大厂,钱还少,感觉不如考公如果🐮u们是我现在这种情况,会怎么选?
负债的混子:关注你一段时间了,突然发现你头像名字都改了,想必是这段时间压力很大。关于就业还是考公的选择,就像很多牛友说的:不要美化自己没走过的路。你现在想往互联网发展,发现这条路很难走,然后想往考公发展,但是你没走过考公这条路,所以你不知道这条路的压力如何。你今年大三了,还有时间给你做选择,我希望你能够尽快的决定自己的方向,然后一条路走到黑,而不是在这里徘徊,每个人的道路是不一样的,你无法复刻别人的路,你能做的就是尽力的完善自己。 最后,我想说的是,加油,陌生人!
点赞 评论 收藏
分享
邮小鼠:粤嵌的项目水的要死 来我们学校带过课程实习 项目名字是车机终端 实际上就是写了了个gui 还是老师把代码发给你你改改的那种
点赞 评论 收藏
分享
粗心的雪碧不放弃:纯学历问题,我这几个月也是一直优化自己的简历,后来发现优化到我自己都觉得牛逼的时候,发现面试数量也没有提升,真就纯学历问题
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务