`

头插法使得链表逆序

 
阅读更多

        代码也很简单,空间复杂度为O(1)。

算法描述,pre记录前一个node,current记录当前node,temp存储current的下一个node。这样就形成了一个循环,temp存储current的下一个node之后又current的next指向pre节点;这样就逆序了一个节点。然后pre和current整体后移一位,继续逆序第二个节点。以此类推。

typedef struct Node{
	int value;
	struct Node *next;
}node;

node* reverseList(node* head)
{
	if(head==NULL || head->next==NULL)
	{
		return head;
	}
	node *pre=NULL;
	node *current=head;
	node *temp;
	while(current!=NULL)
	{
		temp=current->next;
		current->next=pre;
		pre=current;
		current=temp;
	}
	return pre;
}
int main()
{
	node arr[5]={1,&arr[1],2,&arr[2],3,&arr[3],4,&arr[4],5,NULL};
	node *p=reverseList(arr);

	while(p!=NULL)
	{
		printf("%d\n",*p);
		p=p->next;
	}
	system("pause");
	return 0;
}

 

分享到:
评论

相关推荐

    链表的基本操作(插入、删除、显示,逆序等)

    这种非顺序存储方式使得链表在某些操作上具有优势,如插入和删除。 1. **链表的建立** 链表的建立通常从创建一个空链表开始。一个空链表只有一个头节点,它的值通常为NULL,表示链表没有元素。创建链表时,我们...

    数据结构链表排序数据结构课设,链表排序,升序,逆序,倒置

    4. 倒置排序:倒置排序不同于升序和降序,它并不改变元素的大小关系,而是改变节点间的连接,使得链表的前后顺序反转。这可以通过双指针法实现,设置两个指针,一个在前一个在后,交换它们指向的节点,然后逐步向...

    链表_数据结构--链表_

    `1.1链表的逆序(1).py`和`1.3链表的逆序_插入法.py`可能展示了不同的链表逆序方法。链表的逆序操作可以是迭代或递归的,其目标是改变节点间的指针方向,使得原链表的最后一个节点成为新的头节点,而原头节点则成为新...

    第一课 链表

    2. **头插法**:从第二个节点开始,依次将其插入到第一个节点之前,最后将原始链表的头节点设为新链表的最后一个节点。这种方法虽然也需要遍历链表,但会创建新的节点引用,因此需要更多的空间。 接下来的几个问题...

    leetcodeoj和leetcode-leetcode-in-java:这是leetcode学习笔记。(在Java中)

    链表逆序之头插法,关键代码(牢记): pre.next = cur.next; cur.next = head.next; head.next = cur; cur = pre.next; 3 . Add-TwoNum 要点: - 分别考虑相加的两个链表长度相同和不同的情况 - 代码...

    C语言对链表的基本操作

    这种灵活性使得链表在处理动态数据集合时具有显著优势。下面我们将详细探讨C语言中链表的基本操作。 1. **链表的定义** 在C语言中,链表由一系列节点组成,每个节点包含数据部分和指向下一个节点的指针部分。一个...

    线性表的链式存储结构

    2、头插法建立单链表:头插法是在链表头部插入新节点的方法。首先创建一个新的节点,然后将其next指针指向当前链表的头结点,最后将头结点的next指针更新为新节点。重复此过程n次,即可建立一个长度为n的带头结点的...

    数据结构链表操作大全

    - **逆序建表(头插法)**:从尾开始,依次在链表头部插入节点。 3. **链表操作**: - **插入操作**:在指定位置插入节点,需要找到前驱节点,并更新指针关系。 - **删除操作**:删除指定节点,需要修改前驱节点...

    用C写的链表的值查询

    相较于数组,链表具有动态扩展、不连续存储等特性,使得它在处理插入、删除等操作时更具优势。本话题将深入探讨如何在C语言中实现链表的值查询。 首先,我们需要了解链表的基本概念。链表由一系列节点组成,每个...

    第2章_线性表2.pdf

    链表的创建可以分为逆序建表(头插入法)和正序建表(尾插入法)。头插入法是将新节点插入到链表的头部,正序建表则是在链表尾部插入新节点,并使用一个尾指针`r`来维护当前链表的尾部位置。 逆序建表是一种简单的...

    单链表的逆置的概要介绍与分析

    - **通过头插法重建逆序链表**:这种方式是在原链表的基础上不改变其结构,而是创建一个新的链表,然后采用头插法逐个将原链表的节点插入新链表中,从而形成一个逆序的新链表。 其中,迭代方法中的“借助额外指针...

    LinkList_Example_linklist_

    这可能包括在链表的开头(头插法)或末尾(尾插法)插入节点,也可能包括在指定位置插入节点。 4. 删除操作:删除操作通常需要找到要删除的节点,然后更新其前一个节点的指针以指向其后一个节点。如果删除的是头...

    Double_List_and_Sort.rar_双链表

    这样的设计使得在链表中的前后移动变得更为灵活,同时也方便了对链表的插入和删除操作。 在双链表中,节点通常由三部分组成:数据域,存放实际的数据;前向指针,指向当前节点的前一个节点;后向指针,指向当前节点...

    LinkList.txt

    - **创建链表**:文件中提供了两种创建链表的方法,一种是逆序插入法,另一种是正序插入法。这两种方法的主要区别在于插入新节点的位置不同。逆序插入是在链表头部插入新节点,而正序插入是在链表尾部进行插入。 ...

    安徽省公务员计算机专业知识程序设计题专题

    - **头插法**:在链表的头部插入节点。这种方式下,节点的插入顺序与最终链表中元素的顺序相反。这种方法的优点在于实现简单,但可能导致链表元素的逆序排列。 ```c LinkList Create_LinkList1() { LinkList L = ...

    数据结构基本概念.docx

    头插法建表逆序、尾插法建表顺序。查找、插入、删除等操作都需要遍历链表。 静态链表是用一维数组来实现线性链表,这种用一维数组表示的线性链表,称为静态链表。静态链表的容量是一定的,链表的插入与删除同前面所...

    使用C++实现的基于链表的大整数类(数据结构实验)

    这使得链表在处理大整数时非常灵活,因为我们可以在需要时动态添加或删除节点。 首先,我们需要创建一个节点类(Node),它包含一个存储单个数字的成员变量和一个指向下一个节点的指针。节点类可以定义如下: ```...

    SHW1线性表报告1

    3. 学生成绩管理的例子中,建议使用链表作为数据结构,通过头插法实现按学号逆序输出。输入、建立和插入操作的时间复杂度均为O(n),无需查找操作。 4. 医院看病排队管理涉及的问题包括模拟真实情况、病人分类、科室...

    算法大全-面试题-数据结构

    11. **用链表模拟大整数加法运算**:将大整数转化为链表,逐位相加并处理进位,最后将结果链表逆序输出。 12. **单链表排序**:可以使用插入排序、归并排序等算法,链表的特性使得这些排序算法在链表上的实现有别于...

    数据结构试题及答案 (2)1

    6. **散列表**:在处理冲突时,开放定址法的平均查找长度通常高于链接法,因为链接法通过链表连接冲突的元素,而开放定址法则需要不断地寻找下一个空槽位。 7. **形参与实参**:如果需要形参直接访问实参,应该使用...

Global site tag (gtag.js) - Google Analytics