C++笔试题之实现单链表两两反转（置换）

C++笔试题之实现单链表两两反转（置换）

两两反转单链表就是把每两个数反转一次。如：

A -> B -> C ->D -> E -> F两两反转后变为 B -> A -> D ->C -> F -> E。

具体代码如下：

#include using namespace std;struct Node{ int data; Node* next;};void Display(Node *head)// 打印链表{ if (head == NULL) { cout << "the list is empty" << endl; return; } else { Node *p = head; while (p) { cout << p->data << " "; p = p->next; } } cout << endl;}Node* ReverseList(Node* head)// 两两反转链表{ if (head == NULL) return NULL; Node* cur = head; //记录下下个结点，下次的置换在该结点和该结点的下一个结点间进行 Node * nexnex = cur->next->next; //置换当前结点和下一个结点，例如，这一步后B指向A了，但是A依然指向B，目标是要A指向D。 Node * swaphead = cur->next; swaphead->next = cur; //递归,返回D Node * swapnexnex = ReverseList(nexnex); //使A指向D cur->next = swapnexnex; //最后返回B return swaphead;}Node* Init(int num) // 创建链表{ if (num <= 0) return NULL; Node* cur = NULL; Node* head = NULL; Node* node = (Node*)malloc(sizeof(Node)); node->data = 1; head = cur = node; for (int i = 1; i < num; i++) { Node* node = (Node*)malloc(sizeof(Node)); node->data = i + 1; cur->next = node; cur = node; } cur->next = NULL; return head;}int main( ){ Node* list = NULL; list = Init(10); Display(list); Node* newlist = ReverseList(list); Display(newlist); system("pause"); return 0;}

这里用到了递归，关于递归函数内部的执行顺序详见：​

整个两两反转过程如下所示：

​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。