逻辑图如下所示:
只需要将需要反转的节点放到头节点位置即可,
使用两个指针一个指针指向需要反转的节点,另一个指针指向需要反转的指针的前驱节点(其实也就是元链表的头节点)
操作过程:
- 1 2 3 4 5
- 2 1 3 4 5
- 3 2 1 4 5
- 4 3 2 1 5
- 5 4 3 2 1
//单项链表的原地反转
/* * 逻辑:* 使用两个指针 prev 和 pCur ,pCur是需要反转的结点,prev为需要反转的结点的前驱结点* prev的指针域指向需要反转结点的下一个结点* 将pCur反转到prev之前* 将头指针的next指向反转后的结点* pCur指向下一次需要反转的结点** */#include <stdio.h>
#include <stdlib.h>#define TRUE 0
#define FALSE -1typedef int ElemType;typedef struct LNode{ElemType data;struct LNode *next;
}LNode,*LinkList;//初始化
LinkList list_lnit()
{LNode *t;t = (LNode *)malloc(sizeof(LNode));t->next = NULL;LinkList head;head = t;return head;
}//头插法
int head_insert(LinkList head,ElemType data)
{if(NULL == head)return FALSE;//创建一个新的结点LinkList p = (LinkList)malloc(sizeof(LNode));p->data = data;p->next = head->next;head->next = p;return TRUE;
}//打印结点
int print_list(LinkList head)
{if(NULL == head)return FALSE;//使用一个指针对链表进行遍历LNode *t;t = head->next;while (t != NULL){printf("%d ",t->data);t = t->next;}printf("\n");return TRUE;
}//反转算法
LinkList reverse(LinkList head)
{if(NULL == head || NULL == head->next)return head;LNode *prev, *pCur;// prev 指向第一个数据结点prev = head->next;// pCur 指向第二个数据结点pCur = prev->next;if(pCur == NULL)//如果只有一个数据结点则不需要反转return head;while (pCur != NULL){prev->next = pCur->next;pCur->next = head->next;head->next = pCur;pCur = prev->next;}return head;
}int main()
{LinkList head;head = list_lnit();int i;for (i = 0; i < 5;i++){head_insert(head,100+i);}print_list(head);head = reverse(head);print_list(head);return 0;
}
运行结果: