给你一个链表以及一个k,将这个链表从头指针开始每k个翻转一下。
链表元素个数不是k的倍数,最后剩余的不用翻转。
样例:
给出链表 1->2->3->4->5
k = 2, 返回 2->1->4->3->5
k = 3, 返回 3->2->1->4->5
#ifndef C450_H
#define C450_H
#include<iostream>
#include<stack>
using namespace std;
class ListNode{
public:
int val;
ListNode *next;
ListNode(int val)
{
this->val = val;
this->next = NULL;
}
};
class Solution {
public:
/* * @param head: a ListNode * @param k: An integer * @return: a ListNode */
ListNode * reverseKGroup(ListNode * head, int k) {
// write your code here
if (head == NULL || k == 1)
return head;
ListNode *p = head;
int num = 0;
while (p != NULL)
{
num++;
p = p->next;
}
if (k > num)
return head;
stack<int> sk;
ListNode *q = head;
ListNode *node = new ListNode(-1);
ListNode *t = node;
int n = 1;
while (q != NULL)
{
if (n%k != 0)
{
sk.push(q->val);
}
else
{
t->next = new ListNode(q->val);
t = t->next;
while (!sk.empty())
{
t->next = new ListNode(sk.top());
sk.pop();
t = t->next;
}
}
++n;
q = q->next;
}
ListNode *l = t->next;
while (!sk.empty())
{
t->next = new ListNode(sk.top());
t->next->next = l;
l = t->next;
sk.pop();
}
return node->next;
}
};
#endif