赞
踩
采用非递归(迭代)的方法,不需要额外的空间。
算法图解参见:
数据结构学习-带头结点的单链表就地逆置
单链表的逆置(头插法和就地逆置)
算法用到三个指针,PreviousPos, CurrentPos, NextPos,在开头到 PreviousPos的节点已经排序好,从 CurrentPos 到尾节点之间未排序好。
链表带有头节点,但头节点先分离出来,最后排序好后加上。
#include<stdio.h> #include<stdlib.h> struct node; typedef struct node *ptrtonode; typedef ptrtonode list; typedef ptrtonode position; struct node { int data; ptrtonode next; }; list InitList(void); void CreatList(list L); void ShowList(list L); void ReverseList(list L); void DeleteList(list L); int main(void) { list L = InitList(); CreatList(L); puts("\nOriginal list:"); ShowList(L); ReverseList(L); puts("\nReversed list:"); ShowList(L); DeleteList(L); return 0; } list InitList(void) { list L = (list)malloc(sizeof(struct node)); if (L == NULL) { fprintf(stderr,"Out of sapce\n"); exit(EXIT_FAILURE); } L->next = NULL; return L; } void InsertTail(int n, position p) { list tem = InitList(); tem->data = n; tem->next = p->next; p->next = tem; } void eatline(void) { while (getchar() != '\n') continue; } void CreatList(list L) { printf("Please enter numbers (nonumeric values to stop):\n"); position p = L; int n; while (scanf("%d",&n) == 1) { InsertTail(n,p); p = p->next; } eatline(); } void ShowList(list L) { position p = L->next; while (p) { printf("%d ",p->data); p = p->next; } putchar('\n'); } void ReverseList(list L) { position curpos, nextpos, prepos, pfirst; pfirst = L->next;//pfirst指向第一个节点 prepos = NULL; curpos = pfirst; nextpos = pfirst->next; while (nextpos != NULL) { //每一次循环将curpos指向prepos, //curpos指向节点逆置成功, //再将所有指针向后移动 curpos->next = prepos; prepos = curpos; curpos = nextpos; nextpos = nextpos->next; } //循环结束后curpos指向最后一个节点, //nextpos指向NULL,因此需要逆置curpos指向节点 curpos->next = prepos; //逆置完成curpos指向第一个节点 //最后将头节点添加 L->next = curpos; } void DeleteList(list L) { position p = L->next, tem; L->next = NULL; while (p) { tem = p->next; free(p); p = tem; } }
测试结果:
Please enter numbers (nonumeric values to stop):
3 2 0 8 9 1
q
Original list:
3 2 0 8 9 1
Reversed list:
1 9 8 0 2 3
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。