一、题目
设计一个算法,实现将头结点为head的单链表就地逆置,即利用原带头结点单链表head的结点空间将数据元素序列(a0,a1,…,an-1)逆置为(an-1,…, a1,a0)。
本题所使用的数据结构定义如下:
typedef int ElemType ;
单链表的数据结构定义:
typedef struct Lnode
{ ElemType data; /* 数据域,保存数据元素(结点的值) */
struct Lnode *next; /* 指针域 */
}LinkList; /* 结点的类型 */
二、算法思路
1、若单链表为空表或单链表中只有一个元素,则无需进行逆置。
2、若单链表有两个或两个以上的元素,则定义指针p指向首元结点,定义指针q指向首元结点的下一个结点。
3、通过改变头指针、指针p、指针q所指的结点的指针域的指向来改变链表中的结点顺序,使q所指结点移动到首元结点的位置。文章来源:https://www.toymoban.com/news/detail-718118.html
4、将指针p和指针q后移一位,重复进行操作3,直到遍历整个链表,即q指向空为止。此时得到的是就地逆置后的链表。文章来源地址https://www.toymoban.com/news/detail-718118.html
三、程序实现
void reverseList(LinkList*head) {
if (head->next == NULL || head->next->next == NULL) {//判断单链表是否为空表或只有一个元素
return;
}
LinkList* p = head->next;//定义指针p指向首元结点
LinkList* q = p->next;//定义指针q指向首元结点的下一个结点
while (q) {//若q不为空,则进入循环
p->next = q->next;//使q所指结点移动到首元结点的位置
q->next = head->next;
head->next = q;
q = p->next;//将指针p和指针q后移一位
}
}
到了这里,关于数据结构(C语言):将单链表就地逆置的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!