链表问题 反转链表k节点反转链表

链表数据结构

struct node { string value; node *next = NULL; };

 

单链表的反转

用指针pre、cur、next分别指向前一个节点、当前节点、后一个节点，我们的目标是将cur节点的next指针指向pre，这样便反转了，当然在反转之前需要记住原先cur节点的next指针所指向的节点。

node * reverse(node * head) { node* pre = NULL; node* cur = head; node* next; while(cur) { next = cur->next; cur->next = pre; pre = cur; cur = next; } return pre; }

 

每k个节点进行反转，不足k个节点不反转

如：1->2->3->4->5->6->7->8，k=3；

结果：3->2->1->6->5->4->7->8

 

node* reverseKnode(node* head,int k) { node* newRoot = new node; node* pre = newRoot; node* cur = head; node* start = head; node* end = head; node* next = head; while(next) { for(int i=1;i<k && end!=NULL;i++) { end = end->next; } if(end == NULL)//没有这句话就是不足k个节点也会反转 { break; } cout<<end->value<<endl; next = end->next; end->next = NULL; node* newStart = reverse(start); node* newEnd = start; pre->next = newStart; newEnd->next = next; start = next; pre = newEnd; end = start; } return newRoot->next; }