链表逆置相关算法题|原地逆置|轮转链表|循环链表逆置(C)

原地逆置

试编写算法将带头结点的单链表就地逆置，所谓“就地”是指辅助空间复杂度为O(1)。

思路1

将头节点摘下，然后从第一节点开始，依次插入到头节点后面，头插法建立单链表，直到最后一个节点为止

断开L和链表

将cur的next指向L的next

将L的next指向cur

完成插入，将cur指向next，next指向cur的next

LinkList ReverseL(LinkList &L)
{
	LNode* cur, *next;
	cur = L->next;
	L->next = NULL;
	while (cur)
	{
		next = cur->next;
		cur->next = L->next;
		L->next = cur;
		cur = next;
	}
	return L;
}

一个工作指针cur用来遍历链表，一个后继指针next用来保存cur的下一个节点
cur指向第一个节点，将哨兵位的next置为NULL，与后面的链表断开链接
cur往后遍历，直到cur指向NULL
将next指向cur的next，保存下一个节点
将cur的next指向哨兵位的next，将cur节点插入到哨兵节点之后
将L的next指向cur，将哨兵节点和当前节点进行链接
将cur指向next，继续往后遍历
最后返回链表L

思路2

用三个指针prev，cur，next来表示三个连续的节点

处理第一个节点，cur的next指向NULL

prev指向cur，cur指向next，next指向next的next

cur的next指向prev

直到next指向NULL

最后将L的next指向cur节点，也就是原来的尾节点

完成逆置

LinkList ReverseL(LinkList &L)
{
	LNode* prev, *cur = L->next, *next = cur->next;
	cur->next = NULL;
	while (next)
	{
		prev = cur;
		cur = next;
		next = next->next;
		cur->next = prev;
	}
	L->next = cur;
	return L;
}

一个工作指针cur用来遍历链表，一个后继指针用来保存cur的下一个节点，一个前驱指针prev用来保存前一个节点
cur指向L的next，从第一个节点开始
将当前遍历的节点的next指向NULL
开始遍历：
将prev指向cur，cur指向next，next指向next的下一个，三个指针往后走一步
将cur的next指向perv，将中间节点的next指向前一个节点
直到第三个节点指向NULL，也就是最后一个节点的next指向倒数第二个节点
最后将L的next指向cur，也就是哨兵位头节点指向最后一个节点，完成逆置
返回链表L

轮转链表

设将n$(n>1)$个整数存放到不带头结点的单链表L中，将L中保存的序列循环右移k$(0<k<n)$个位置。例如，若k=1，则将链表{0,1,2,3}变为{3,0,1,2}。

算法思想

首先，遍历链表计算表长n，并找到链表的尾节点，将其与头节点相连，构成一个循环单链表
然后找到新链表的尾节点，为原链表的第n-k个节点，令L指向新链表尾节点的下一个节点，并将环断开，得到新链表

LinkList* Converse(LinkList &L, int k)
{
	int n = 1;
	LNode* cur = L;
	while (cur->next)
	{
		cur = cur->next;
		n++;
	}
	cur->next = L;
	for (int i = 1; i <= n - k; i++)
	{
		cur = cur->next;
	}
	L = cur->next;
	cur->next = NULL;
	return L;
}

将n初始化为1，cur指向L，cur的next指向第一个节点，往后遍历直到cur的next指向NULL，cur指向最后一个节点

再下一次cur->next指向NULL，不进入循环
这样遍历出链表的节点个数

将cur的next指向L

构成循环链表
若k=1，也就是要右移一个位置
新链表的尾节点也就是第n-k个节点，也就是第4-1=3个节点
从头遍历依次，找到第n-k个节点，用cur指针指向

令L指向新链表尾节点的下一个节点

将cur的next指向NULL，断开环

完成右移

循环链表逆置

与逆置单链表的不同之处：

1. 初始化成循环链表而不是空链表
2. 判断链表尾不用空指针而用是否是链表头指针
   

void reverse(LinkList &L)
{
	LNode* cur = L->next, *next;
	L->next = L;           //初始化成空循环链表

	while (cur != L)       //当cur等于L时结束
	{
		next = cur->next;  //暂存cur的后继节点
		cur->next = L->next;
		L->next = cur;
		cur = next;
	}
	return L;
}

让L的next指向自己，循环链表的初始化

用next指针指向cur的下一个节点

将cur的next指向L的next

L的next指向cur

cur指向next

直到cur指向L
完成逆置