分析:
初始化三个指针p1,p2,p3. p1指向当前结点,p2指向当前结点的下一个结点,p3指向当前结点的上一个结点。则初始值p1,p2,p3分别是:p1指向第一个结点,p2指向第二个结点,p3指向p1的上一个结点,则p1的初始值为NULL。
逆序后p1->next = p3.
紧接着让p1,p2,p3指针向后移,重复以上操作p1->next = p3,直到p2为空。则p1就是单链表的最后一个结点,让单链表的头结点指向p1,就完成了单链表的逆序操作。
#include <stdio.h> #include <stdlib.h> typedef int ElemType; //定义链表的存储结构 typedef struct Node { ElemType data; struct Node *next; } Node; typedef struct Node *LinkList; typedef struct Node *pNode; //创建单链表(带头结点的单链表) LinkList createLinkList(int n, int isCycle); //单链表逆序 int reverseLinkList(LinkList *L); //遍历单链表 void traversalList(LinkList L); //创建单链表 LinkList createLinkList(int n, int isCycle) { LinkList L = (pNode)malloc(sizeof(Node)); //头结点 pNode p, r = L; ElemType e; for (int i = 0; i < n; i++) { printf("请输入第%d个数字", i + 1); scanf("%d", &e); p = (pNode)malloc(sizeof(Node)); if (p == NULL) { printf("out of space"); exit(1); } p->data = e; if (i == n-1 && isCycle == 1) { p->next = L; } else { p->next = NULL; } if (L == NULL) { L = p; } else { r->next = p; } r = p; } return L; } //单链表逆序 int reverseLinkList(LinkList *L) { pNode p1, p2, p3; p1 = (*L)->next; //p1指向第一个结点 if (p1 == NULL) { //链表为空 return 0; } p2 = p1->next; //p2指向第二个结点 p3 = NULL; //p3指向p1的前一个结点,故p3的初始值为NULL p1->next = p3; //逆序后,p1的下一个结点就应该是p3 while (p2) { p3 = p1; p1 = p2; p2 = p2->next; p1->next = p3; } (*L)->next = p1; return 1; } //遍历单链表 void traversalList(LinkList L) { pNode p = L->next; while (p) { printf("%d", p->data); p = p->next; } } int main(int argc, const char * argv[]) { LinkList L = createLinkList(5, 0); traversalList(L); reverseLinkList(&L); traversalList(L); return 0; }