链表逆置的两种方法-Toy模板网

这篇具有很好参考价值的文章主要介绍了链表逆置的两种方法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

原链表图：

链表逆置,每日一学,链表,数据结构

方法一：头插法链表逆置

1.断开头节点与其他节点的连接（提前存好head->next的地址）

Node* p = head->next;

Node* q = p->next;

head->next = NULL; 链表逆置,每日一学,链表,数据结构

2. 头插法在head后面插入p后链表的各个节点

p->next = head->next;

head->next = p;

p、q指针往后移

p = q;

if (q != NULL)

q = q->next;

链表逆置,每日一学,链表,数据结构

3. 依此类推直到全部插入，链表逆置完成

链表逆置,每日一学,链表,数据结构

完整代码：

void R_head(List head)
{
	assert(head != NULL);
	if (head == NULL)
		return;
	if (GetLength(head) <= 1)
		return;
	Node* p = head->next;
	Node* q = p->next;
	head->next = NULL;
	while (p != NULL)
	{
		p->next = head->next;
		head->next = p;
		p = q;
		if (q != NULL)
			q = q->next;
	}
	return;
}

方法二：三个指针直接逆置

1.设置三个指针分别指向head后面的三个节点

Node* p = head->next;

Node* q = p->next;

Node* r = q->next;

链表逆置,每日一学,链表,数据结构

2. p第一个指向的节点（head->next）的指针域赋为空

p->next = NULL;

链表逆置,每日一学,链表,数据结构

3. 把q的next指向q，然后p，q，r往后移（r是为了存逆置前q的next）

q->next = p;

p = q;

q = r;

r = r->next;

链表逆置,每日一学,链表,数据结构

4. 当r指向空时，不再后移，将head的next指向q

q->next = p;

plist->next = q;

链表逆置,每日一学,链表,数据结构

完整代码：

void R(List head)
{
	assert(head != NULL);
	if (head == NULL)
		return;
	if (GetLength(head) <= 1)
		return;
	Node* p = head->next;
	Node* q = p->next;
	Node* r = q->next;
	p->next = NULL;
	while (r != NULL)
	{
		q->next = p;
		p = q;
		q = r;
		r = r->next;
	}
	q->next = p;
	head->next = q;
}

三指针相对复杂。

如果链表长度为1或0则不需要逆置直接return。文章来源地址https://www.toymoban.com/news/detail-597340.html

到了这里，关于链表逆置的两种方法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！