题解 | #链表中的节点每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个一组翻转链表的精髓,这是我通过努力记住了这个方法,为自己感到自豪。

全部评论

相关推荐

沉淀一会:**圣经 1.同学你面试评价不错,概率很大,请耐心等待;2.你的排名比较靠前,不要担心,耐心等待;3.问题不大,正在审批,不要着急签其他公司,等等我们!4.预计9月中下旬,安心过节;5.下周会有结果,请耐心等待下;6.可能国庆节前后,一有结果我马上通知你;7.预计10月中旬,再坚持一下;8.正在走流程,就这两天了;9.同学,结果我也不知道,你如果查到了也告诉我一声;10.同学你出线不明朗,建议签其他公司保底!11.同学你找了哪些公司,我也在找工作。
点赞 评论 收藏
分享
好的h:其实像点评那里的mq可以去掉我觉得,一个单体架构为什么要上mq呢,这就是明显的炫技,而且是很低级的炫技。mq为的在消费端解耦,消费端和服务端都部署在本机上怎么去解耦,那我为什么不多开几条线程去解决问题呢?真的兄弟,面试的时候突然问你这个你能扛住吗。
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务