首页 > itarticle > 25. reverse nodes in k

25. reverse nodes in k

admin 11月 13, 2020 0

题目描述

与 leetcode 24 相似。
给一个链表，每 k个节点反转，如 1 -> 2 -> 3 -> 4 -> 5，
当 k = 2时，2 -> 1 -> 4 -> 3 -> 5；
当 k = 3时，3 -> 2 -> 1 -> 4 -> 5。

题目分析

先保证当前节点有k个后继节点，接着以最后节点为界，将其变为两个链表，
然后将前链表反转，最后再拼为一个链表。

代码

#include <iostream>

struct ListNode {
  int val;
  ListNode* next;
  ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
  ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode root(0);
    root.next = head;
    ListNode* ptr1 = &root;
    while (ptr1) {
      int n = k;
      ListNode* ptr2 = ptr1;
      while (n > 0 && ptr2->next != NULL) {
        --n;
        ptr2 = ptr2->next;
      }
      if (n > 0) {
        break;
      }
      ListNode* tmp1 = ptr1->next;
      ListNode* tmp2 = ptr2->next;
      ptr2->next = NULL;
      reserve(ptr1->next, &ptr1);
      tmp1->next = tmp2;
      ptr1 = tmp1;
    }
    return root.next;
  }
  void reserve(ListNode* ptr, ListNode** newPtr) {
    if (ptr == NULL) {
      return ;
    }
    reserve(ptr->next, newPtr);
    (*newPtr)->next = ptr;
    *newPtr = (*newPtr)->next;
  }
};

总结

1次AC