【说明】：
本文是左程云老师所著的《程序员面试代码指南》第二章中“将单链表的每K个节点之间逆序”这一题目的C++复现。
本文只包含问题描述、C++代码的实现以及简单的思路，不包含解析说明，具体的问题解析请参考原书。
感谢左程云老师的支持。
【题目】：
给定一个单链表的头节点 head，实现一个调整单链表的函数，使得每K个节点之间逆序，如果最后不够K个节点一组，则不调整最后几个节点。
例如：
链表：1->2->3->4->5->6->7->8->NULL，K = 3.
调整后为：3->2->1->6->5->4->7->8->NULL。其中7、8不调整，因为不够一组。
【思路】：
解法一：使用栈，每K个清空栈来进行逆序。
解法二：需要保存即将逆序的K个节点的前一个节点pre和后一个节点next
【编译环境】：
CentOS6.7（x86_64）
gcc 4.4.7
【实现】：
实现及测试代码：
/*
*文件名：list_reverse.cpp
*作者：
*摘要：将单链表的每K个节点之间逆序
*/ #include <iostream>
#include <stack> using namespace std; class Node
{
public:
Node(int data)
{
value = data;
next = NULL;
}
public:
int value;
Node *next;
}; Node* resign1(stack<Node*> &s,Node *left,Node *right)
{
Node *cur = s.top();
s.pop();
if(NULL != left)
left->next = cur;
Node *next = NULL;
while(!s.empty())
{
next = s.top();
s.pop();
cur->next = next; //反转
cur = next;
}
cur->next = right;
return cur;
} Node* reverseKNodes1(Node *head,int K)
{
if(K < )
return head;
stack<Node*> s;
Node *newHead(head),*cur(head),*pre(NULL),*next(NULL);
while(NULL != cur)
{
next = cur->next;
s.push(cur);
if(s.size() == K)
{
pre = resign1(s,pre,next);
newHead = newHead == head ? cur : newHead;
}
cur = next;
}
return newHead;
} void resign2(Node *left,Node *start,Node *end,Node* right)
{
Node *pre = start;
Node *cur = start->next;
Node *next = NULL;
while(cur != right)
{
next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
if(NULL != left)
left->next = end;
start->next = right;
} Node* reverseKNodes2(Node *head,int K)
{
if( > K)
return head;
Node *cur(head),*start(NULL),*pre(NULL),*next(NULL);
int count = ;
while(NULL != cur)
{
next = cur->next;
if(count == K)
{
start = pre == NULL ? head : pre->next;
head = pre == NULL ? cur : head; //第一次发生变化的时候确定head
resign2(pre,start,cur,next);
pre = start;
count = ;
}
count++;
cur = next;
}
return head;
} void printList(Node *head)
{
while(NULL != head)
{
cout << head->value << " ";
head = head->next;
}
cout << endl;
} int main()
{
Node *head = NULL;
Node *ptr = NULL; for(int i =;i<;i++)//构造链表
{
if(NULL == head)
{
head = new Node(i);
ptr = head;
continue;
}
ptr->next = new Node(i);
ptr = ptr->next;
}
cout << "Before reverse:" << endl;
printList(head);
cout << "First reverse:" << endl;
head = reverseKNodes1(head,);
printList(head);
cout << "Second reverse:" << endl;
head = reverseKNodes2(head,);
printList(head);
return ;
}
注：
转载请注明出处；
转载请注明源思路来自于左程云老师的《程序员代码面试指南》。