【问题描述】

设计一个算法,将链表中所有结点的链接方向“原地”逆转，即要求仅利用原表的存储空间，换句话说，要求算法的空间复杂度为 O(1)。

【参考代码】

typedef struct LNode
{
	int data;
	struct LNode* next;
}LNode, * LinkList;
void Inverse(LinkList &La)
{
	LinkList pa, p;
	pa = La->next;
	La->next = NULL;  //头插法
	while (pa)
	{
		p = pa->next;
		pa->next = La->next;
		La->next = pa;       //pa插入头结点之后
		pa = p;
	}
}

【代码解析】

本代码针对考研数据结构，采用伪代码实现，主要关注代码逻辑。

本题实现逆转相对简单，只需要依次读入，再经过头插法即可实现。