详见: http://blog.yemou.net/article/query/info/tytfjhfascvhzxcyt114
反转单链表的几种方法
最近试着做一些笔试面试题,既是为来年找工作做准备,也可以做为数据结构和算法的复习笔记,就陆续发在这里吧,有需要的朋友可以看一下,如果有没考虑周全的地方欢迎指正。
先来一个最常见的题目:反转单链表。假设单链表的数据结构定义如下:
typedef struct LNode
{ int data;
struct LNode *next;
}LNode, *LinkedList; |
并且这个单链表有一个头指针list指向第一个结点,最后一个结点指向NULL,很容易理解。
最容易想到的第一种方法就是重新建立一个单链表newList,每次将list中的第一个结点放到newList后面。注释比较详细,所以就不具体说了,直接看代码吧:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
LinkedList ReverseSinglyLinkedList(LinkedList list) { LinkedList newList; //新链表的头结点
LNode *tmp; //指向list的第一个结点,也就是要摘除的结点
//
//参数为空或者内存分配失败则返回NULL
//
if (list == NULL || (newList = (LinkedList) malloc ( sizeof (LNode))) == NULL)
{
return NULL;
}
//
//初始化newList
//
newList->data = list->data;
newList->next = NULL;
//
//依次将list的第一个结点放到newList的第一个结点位置
//
while (list->next != NULL)
{
tmp = newList->next; //保存newList中的后续结点
newList->next = list->next; //将list的第一个结点放到newList中
list->next = list->next->next; //从list中摘除这个结点
newList->next->next = tmp; //恢复newList中后续结点的指针
}
//
//原头结点应该释放掉,并返回新头结点的指针
//
free (list);
return newList;
} |
第二种方法是每次都将原第一个结点之后的那个结点放在list后面,下图是原始的单链表。
为了反转这个单链表,我们先让头结点的next域指向结点2,再让结点1的next域指向结点3,最后将结点2的next域指向结点1,就完成了第一次交换,顺序就变成了Header-结点2-结点1-结点3-结点4-NULL,然后进行相同的交换将结点3移动到结点2的前面,然后再将结点4移动到结点3的前面就完成了反转,思路有了,就该写代码了:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
LinkedList ReverseSinglyLinkedList(LinkedList list) { LNode *tmp = NULL;
LNode *p = NULL;
if (list == NULL)
{
return NULL;
}
tmp = list->next;
while (tmp->next != NULL)
{
p = tmp->next;
tmp->next = p->next;
p->next = list->next;
list->next = p;
}
return list;
} |
第三种方法跟第二种方法差不多,第二种方法是将后面的结点向前移动到头结点的后面,第三种方法是将前面的结点移动到原来的最后一个结点的后面,思路跟第二种方法差不多,就不贴代码了。
我只想到这三种方法,如果你还知道其它方法,欢迎留言告诉我,多谢。
相关推荐
本文将深入探讨两种方法来反转单链表,这些方法是基于Java编程语言实现的,因此相关知识点包括链表操作、递归以及迭代。 首先,我们需要了解单链表的基本结构。在Java中,一个简单的单链表节点可以定义为: ```...
单链表的操作是面试中经常会遇到的问题,今天总结一下反转的几种方案: 1 ,两两对换 2, 放入数组,倒置数组 3, 递归实现 代码如下: #include #include typedef struct Node { int data; struct Node *...
单链表是一种常见的线性数据结构,其中每个元素包含一个指向下一个元素的指针。就地反转指的是在不使用额外的数据结构的情况下,改变链表中各节点之间的连接关系,使链表的顺序完全颠倒。 #### 代码解析 ##### ...
在C语言中使用类来实现单链表的操作是一种非常实用的方法,尤其当需要对链表进行复杂的管理时。本篇将基于提供的`node.h`头文件和`node.cpp`源代码,详细阐述如何通过类的方式在C语言中实现单链表的基本操作,包括...
以上就是单链表常见的几种面试算法及其实现方法。这些算法不仅在面试中经常被提及,在实际工作中也十分有用。掌握它们不仅能提高你的编程能力,还能加深你对数据结构的理解。希望本文对你有所帮助!
在单链表中插入节点有几种常见情况: 1. 插入到头部:新节点作为新的头节点,原头节点成为新节点的下一个节点。 2. 插入到尾部:遍历链表找到最后一个节点,将新节点插入其后。 3. 插入到指定位置:需找到目标位置的...
在这个"数据结构试验 单链表的基本操作及应用"中,我们可能会涉及以下几个关键知识点: 1. **链表的创建**:首先,我们需要理解如何初始化一个空链表。这通常通过创建一个头节点来实现,头节点的数据域可能为空,但...
接下来,我们介绍几种反转单链表的方法。 ### 方法一:迭代法 迭代法是最直观且易于理解的方式。我们需要三个指针,分别表示当前节点(curr)、前一个节点(prev)和临时前一个节点(temp)。初始时,prev 指向 ...
在单链表的操作中,主要有以下几种常见操作: 1. **插入节点**:在单链表中插入节点,首先要找到插入位置的前一个节点,然后创建新节点并更新前后两个节点的指针。例如,要在链表中间插入节点,需要找到目标位置的...
同样,这个操作也分为几种情况:删除头节点、删除尾节点和其他位置的节点。删除时需要注意释放被删除节点占用的内存空间,并且正确更新前后节点的指针。 ```c if(1==post) { cur=cur->next; person->next=cur->...
单链表是数据结构中的一种基础且重要的结构,它在计算机科学中有着广泛的应用。本实验将深入探讨如何在单链表上进行各种操作。单链表由一系列节点组成,每个节点包含数据元素以及指向下一个节点的指针。在本实验中,...
要实现单链表的逆序,你可以采用以下几种方法: 1. **迭代法**: 这是最直观的方法,使用三个指针`prev`、`current`和`next`。初始化时,`prev`为空,`current`为头节点。遍历链表,每次迭代将`current`的`next`...
在单链表中插入节点分为几种情况:在链表开头(头部插入)、在链表末尾(尾部插入)以及在链表中的某个特定位置插入。头部插入只需改变头节点即可,尾部插入需要遍历链表找到最后一个节点并进行插入,而在特定位置...
单链表是一种基础的数据结构,它在计算机科学中扮演着重要的角色,特别是在数据存储和算法实现方面。单链表由一系列节点组成,每个节点包含数据元素以及指向下一个节点的引用,最后一个节点的引用通常为null,标志着...
创建非循环单链表通常涉及以下几个步骤: - 定义节点结构:一个节点通常包含数据部分和一个指向下一个节点的指针。 - 初始化头节点:创建一个空链表,头节点的指针指向null。 - 插入节点:根据需求在链表的头部或...
在学习单链表时,还需要注意以下几点: - **空间复杂度和时间复杂度**:链表的空间复杂度主要取决于链表的长度,因为每个节点都需要额外的指针空间。插入和删除操作通常比数组更快,因为它们不需要移动元素,但查找...
在单链表的操作中,有几种常见的基本操作: 1. **创建链表**:初始化一个空链表,通常通过创建一个头节点开始,其后继指针为null。 2. **插入节点**:在链表的特定位置插入新节点,需要找到插入位置的前一个节点,...
反转单链表是常见的链表操作,可以通过迭代或递归实现。迭代方法通常涉及三个指针:前一个节点、当前节点和下一个节点。递归方法则利用函数自身来处理链表的子问题。 ### 6. 合并两个有序链表 将两个已排序的链表...
单链表是一种基础的数据结构,它在计算机科学中扮演着重要的角色,特别是在数据存储和算法实现方面。单链表由一系列节点组成,每个节点包含数据元素以及指向下一个节点的指针。这种数据结构允许动态地添加、删除和...