【自用】链表每k节点反转
作者:
Surx
,
2023-09-12 08:54:55
,
所有人可见
,
阅读 104
#include<iostream>
using namespace std;
struct ListNode
{
double val;
ListNode* next;
ListNode() : val(0), next(NULL) {}
ListNode(int x) : val(x), next(NULL) {}
ListNode(int x, ListNode* next) : val(x), next(next) {}
};
ListNode* create(int n)
{
ListNode* dummy = NULL;
dummy = new ListNode;
ListNode* pre = dummy;
for (int i = 0; i < n; i++)
{
ListNode* p = new ListNode;
cin >> p->val;
pre->next = p;
pre = pre->next;
}
return dummy->next;
}
void print(ListNode* head)
{
while (head)
{
if (head->next == NULL)
cout << head->val << " -> NULL";
else
cout << head->val << " -> ";
head = head->next;
}
cout << endl;
}
/*实现如下函数,对给定一个带头结点的单链
表和一个整数K,要求将链表中的每K个结点
做一次逆转*/
void K_Reverse(ListNode*& head, int k)
{
ListNode* beginning = head;
ListNode* pre_beginning = beginning;
while (beginning)
{
/* 判断后续有没有k个节点 */
ListNode* ahead = beginning;
for (int i = 0; i < k; i++)
{
if (!ahead) return;
ahead = ahead->next;
}
/* 将前方k个节点转向*/
ListNode* prev = beginning;
ListNode* cur = prev->next;
ListNode* nex = cur->next;
for (int i = 1; i < k; i++)
{
if (prev) cur->next = prev;
if (cur) prev = cur;
if (nex) cur = nex;
if (nex->next) nex = nex->next;
}
beginning->next = cur;
/*如果是第一次,更新head*/
if (beginning == head) head = prev;
else pre_beginning->next = prev;
/* 更新beginning*/
pre_beginning = beginning;
beginning = beginning->next;
if (!ahead)
{
pre_beginning->next = NULL; return;
}
}
}
int main()
{
int n, k;
cin >> n >> k;
ListNode* head = create(n);
K_Reverse(head, k);
print(head);
return 0;
}