详见: 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;
} |
第三种方法跟第二种方法差不多,第二种方法是将后面的结点向前移动到头结点的后面,第三种方法是将前面的结点移动到原来的最后一个结点的后面,思路跟第二种方法差不多,就不贴代码了。
我只想到这三种方法,如果你还知道其它方法,欢迎留言告诉我,多谢。
相关推荐
C++ 单链表反转 C++ 单链表反转 C++ 单链表反转
NULL 博文链接:https://128kj.iteye.com/blog/1749238
单链表反转是面试时经常会遇到的问题,之前只是在数据结构里用伪代码实现过单链表反转。为落实亲手编写每一个程序的目标,在这里用java实现反转。方法有很多,这里只写最优的。时间复杂度O(n),空间复杂度O(1)。也...
主要介绍了Python3实现的反转单链表算法,结合实例形式总结分析了Python基于迭代算法与递归算法实现的翻转单链表相关操作技巧,需要的朋友可以参考下
单链表的就地反转
让一个单链表反转,就是头当做尾,尾做头,各个结点的指向反向
单链表的反转是常见的面试题目,下面这篇文章主要给大家介绍了关于单链表实现反转的3种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面来一起学习学习吧
实现了一个简单的java版本的单链表,链表反转和链表是否相交如果相交求相交节点。关于链表是否相交是一次阿里的面试的在线试题,挂的很彻底。然后就在网上找了几个实现思路自己用java做了一个简单的实现....
单链表反转的python实现,简洁详细易于理解,附带注释易于分析
单链表的反转可以使用循环,也可以使用递归的方式 1.循环反转单链表 循环的方法中,使用pre指向前一个结点,cur指向当前结点,每次把cur->next指向pre即可。 代码: class ListNode: def __init__(self,x): self...
这是我在一个项目中搜集的几种方法,来实现字符串的反转,有的是用正则表达式,有的是用Scanner扫描器,有的挺经典的!希望对朋友有所启示!
c++ 实现单链表的反转(原地反转法 && 新建链表插入法)
C#编写的字符串反转 有两种方法。 控制台的程序。
List-LinkedList 单链表就地反转 的代码的一种实现。
带头结点的单链表,将其翻转,输出。typedef struct lnode { int data; struct lnode *next;/*指针域*/ } lnode,*linklist; /**linklist表示struct lnode类型的指针;lnode是别名*/
c#中字符串反转的n中方法,对于初学者来说有帮助!
对数据结构不是很熟,用c++实现的单链表反转,冒泡和选择排序,有问题的话请批评指正
主要介绍了C语言实现单链表反转,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧