链表逆序
http://blog.****.net/yxh0823/article/details/6080163
设链表节点为
- typedefstructtagListNode{
- intdata;
- structtagListNode*next;
- }ListNode,*List;
- typedefstructtagListNode{
- intdata;
- structtagListNode*next;
- }ListNode,*List;
要求将一带链表头List head的单向链表逆序。
分析：
1). 若链表为空或只有一个元素，则直接返回；
2). 设置两个前后相邻的指针p,q. 将p所指向的节点作为q指向节点的后继；
3). 重复2),直到q为空
4). 调整链表头和链表尾
示例：以逆序A->B->C->D为例，图示如下
实现及测试代码如下：
- #include<stdio.h>
- #include<stdlib.h>
- typedefstructtagListNode{
- intdata;
- structtagListNode*next;
- }ListNode,*List;
- voidPrintList(Listhead);
- ListReverseList(Listhead);
- intmain()
- {
- //分配链表头结点
- ListNode*head;
- head=(ListNode*)malloc(sizeof(ListNode));
- head->next=NULL;
- head->data=-1;
- //将[1,10]加入链表
- inti;
- ListNode*p,*q;
- p=head;
- for(inti=1;i<=10;i++)
- {
- q=(ListNode*)malloc(sizeof(ListNode));
- q->data=i;
- q->next=NULL;
- p->next=q;
- p=q;
- }
- PrintList(head);/*输出原始链表*/
- head=ReverseList(head);/*逆序链表*/
- PrintList(head);/*输出逆序后的链表*/
- return0;
- }
- ListReverseList(Listhead)
- {
- if(head->next==NULL||head->next->next==NULL)
- {
- returnhead;/*链表为空或只有一个元素则直接返回*/
- }
- ListNode*t=NULL,
- *p=head->next,
- *q=head->next->next;
- while(q!=NULL)
- {
- t=q->next;
- q->next=p;
- p=q;
- q=t;
- }
- /*此时q指向原始链表最后一个元素，也是逆转后的链表的表头元素*/
- head->next->next=NULL;/*设置链表尾*/
- head->next=p;/*调整链表头*/
- returnhead;
- }
- voidPrintList(Listhead)
- {
- ListNode*p=head->next;
- while(p!=NULL)
- {
- printf("%d",p->data);
- p=p->next;
- }
- printf("/n");
- }