LeetCode 25. K 个一组翻转链表 ：C++

• • 题目表述
  • 代码思路

题目表述

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

代码思路

    1 借助栈，进行逆序
    2 先算出组数以及余数
    3 然后每组依次入栈，再依次出栈插入新链表
    4 最后将余数节点插入新链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode *p = head;
        int num = countNode(head);
        // 标记组数
        int flag = 0, flag1 = 0;
        flag = num / k;
        flag1 = num % k;
        // 辅助栈
        stack<int> s;
        // 新链表头结点
        ListNode *newHead = new ListNode();
        ListNode *h = newHead;
        // 标记遍历组数
        for (int i = 0; i < flag; i++) {
            for (int j = 0; j < k; j++) {
                if (p != NULL) {
                    s.push(p->val);
                    p= p->next;
                }
            }
            for (int j = 0; j < k; j++) {
                if (s.size() != 0){
                    int temp = s.top();
                    s.pop();
                    ListNode *node = new ListNode(temp);
                    h->next = node;
                    h = node;
                }
            } 
        }
        for (int i = 0; i < flag1; i++) {
            if (p) {
                ListNode *node = new ListNode(p->val);
                h->next = node;
                h = node;
                p = p->next;
            }
        }

    return newHead->next;

    }
private:
    int countNode (ListNode *head) {
        ListNode *p = head;
        int num = 0;
        while (p) {
            num++;
            p = p->next;
        }
        return num;
    }
    
};