单链表的就地翻转

主要步骤

1、创立新表 2、打印链表 3、翻转链表 4、销毁链表

核心思想

对于就地翻转链表，关键就是不创立新的空间，而是将指针的指向一一反转，也就是将链表之间一个个的箭头完全调转方向。下中代码中p,q,t一开始指向前三个结点，然后先是实现，p和q的箭头反转，然后借助t帮助p,q进行步进，直到最后所有箭头反转完成，最后将头结点和完成后的首节点连接。

代码演示

#include <stdio.h> #include <stdlib.h> #include <iostream> using namespace std; typedef struct ListNode { int data; struct ListNode* next; }node; void createList(node* head); void transport(node* head); void print(node* head); void destory(node* head); int main(void) { node* head; head = (node*)malloc(sizeof(node)); cout << "***创建链表***" << endl; createList(head); cout << "***原始链表***" << endl; print(head); cout << "***反转链表***" << endl; transport(head); print(head); destory(head); return 0; } void createList(node* head) { //建立带头结点的单链表 node* p = head; cout << "***输入链表***" << endl; int data=-1; while (data != 0) {//以0作为链表结束标志 cin >> data; head = (node*)malloc(sizeof(node)); head->data = data; head->next = NULL; p->next = head; p = head; } return; } void transport(node* head) { //反转链表 node* p = head->next; node* q = p->next; node* t = NULL; p->next = NULL; while (q != NULL) {//q如果指向null说明p指向已经是最后一个元素了，反转结束 t = q->next; q->next = p; p = q; q = t; } head->next = p;//重现将头结点挂上首节点，反转完成 } void print(node* head) { //打印链表 node* temp = head->next; while (temp != NULL) { cout << temp->data << " "; temp = temp->next; } cout << endl; } void destory(node* head) { //销毁链表 node* temp = head; node* p = temp->next; while (p != NULL) { free(temp);//销毁节点 temp = p; p = p->next; } printf("链表已销毁成功！"); }