首页 课程 师资 教程 报名

3种单链表的逆置方法

  • 2022-08-18 10:40:54
  • 692次 星辉

链式存储结构一般有单链表、静态链表、循环链表和双向链表。那么,单链表的逆置方法有哪些?星辉小编来为大家解答。

1.头插法

主要思路:遍历的过程中,将遍历的每一个元素依次插入到表头header之后

代码如下:

void ReverseList(LinkList& head)
{
	LinkList p,q;
	p = head->next;
	head->next = NULL;
	while (p)
	{
		q = p;
		p = p->next;
		q->next = head->next;
		head->next = q;		
	}
}

2.就地逆置法

主要思路:重新创建一个新表,遍历链表依次将元素插入到新表的头结点

代码如下:

void ReverseList(LinkList& L)
{
	LinkList cur ,newlist, p;
	cur = L->next;
	newlist = NULL; 
	while(cur)
	{
		p = cur;
		cur = cur->next;
		p->next = newlist;
		newlist = p; 
	}
	L = newlist;
}

3.递归实现

代码如下(示例):

Status ReverseList(ListLink L)
{
	LinkList p = L;
    if (p && p->next)       //链表为空直接返回,而H->next为空是递归基
        return p;
    LinkList q = ReverseList(p->next); //一直循环到链尾 
    p->next->next =  p;                    //翻转链表的指向
    p->next = NULL;                          //记得赋值NULL,防止链表错乱
    return q;                          //新链表头永远指向的是原链表的链尾
}

以上就是关于“3种单链表的逆置方法”介绍,大家如果想了解更多相关知识,可以关注一下星辉的Java堆栈,里面有更丰富的知识等着大家去学习,希望对大家能够有所帮助。

选你想看

你适合学Java吗?4大专业测评方法

代码逻辑 吸收能力 技术学习能力 综合素质

先测评确定适合在学习

在线申请免费测试名额
价值1998元实验班免费学
姓名
手机
提交