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

全部评论

相关推荐

躺尸修仙中:因为很多92的也去卷中小厂,反正投递简历不要钱,面试不要钱,时间冲突就推,不冲突就面试积累经验
点赞 评论 收藏
分享
Yushuu:你的确很厉害,但是有一个小问题:谁问你了?我的意思是,谁在意?我告诉你,根本没人问你,在我们之中0人问了你,我把所有问你的人都请来 party 了,到场人数是0个人,誰问你了?WHO ASKED?谁问汝矣?誰があなたに聞きましたか?누가 물어봤어?我爬上了珠穆朗玛峰也没找到谁问你了,我刚刚潜入了世界上最大的射电望远镜也没开到那个问你的人的盒,在找到谁问你之前我连癌症的解药都发明了出来,我开了最大距离渲染也没找到谁问你了我活在这个被辐射蹂躏了多年的破碎世界的坟墓里目睹全球核战争把人类文明毁灭也没见到谁问你了😆
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务