文档章节

反转链表

htq
 htq
发布于 2016/07/26 09:41
字数 359
阅读 2
收藏 0
点赞 0
评论 0

要求:定义一个函数,将一个链表反转。链表节点定义如下:

struct ListNode
{
	int data;
	ListNode *m_pNext;
};
思路:所谓反转即将链表中某个节点的原本指向后一个节点的指针域指向前一个节点,如果用pCurrent表示当前处理节点,pPrev表示当前处理节点的前一个节点,则很容易想到,反转即pCurretn->m_pNext=pPrev;但是如果直接这么操作的话,因为当前处理节点的下一个节点(记为pNext)的地址保存在pCurrent->m_pNext中,所以如果直接将当前节点指向前一个节点,则pNext的地址丢失,所以不能直接将pCurretn->m_pNext=pPrev;在这个语句之前,我们应该保存pNext的值,即pNext=pCurrent->m_pNext;
用图表示思路如下:

基于上述思路代码如下:

void reverseList(ListNode * pHead)
{
	ListNode *pCurrent=pHead->m_pNext;//pCurrent的初始值指向第一个节点
	pHead->m_pNext=NULL;//首先断开头节点
	while(pCurrent!=NULL)
	{
		ListNode *pNext=pCurrent->m_pNext;//保存pNext的值,初始值指向第二个节点

		pCurrent->m_pNext=pHead->m_pNext;//每次从原链表中摘下当前处理节点,让其指向反转后链表的第一个节点,初始值为让原链表中的第一个节点的指针域置空
		pHead->m_pNext=pCurrent;//让头节点指向当前结点

		pCurrent=pNext;//将当前节点后移,指向下一个带插入的节点

	}
}


本文转载自:http://blog.csdn.net/htq__/article/details/50880017

共有 人打赏支持
htq

htq

粉丝 19
博文 67
码字总数 1007
作品 3
武汉
反转单链表II

原题   Reverse a linked list from position m to n. Do it in-place and in one-pass.   For example:   Given , and ,   return .   Note:   Given m, n satisfy the follow......

一贱书生 ⋅ 2016/12/20 ⋅ 0

面试题16:反转链表

题目:定义一个函数,输入一个链表的头结点,反转该链表并输出反转后链表的头结点。 假设有链表A->B->C->D->E->F->G。在反转链表过程中的某一阶段,其链表指针指向为:A<-B<-C<-D E->F->G。也...

嗯哼9925 ⋅ 2017/12/21 ⋅ 0

92. Reverse Linked List II。

Reverse a linked list from position m to n. Do it in-place and in one-pass. For example: Given 1->2->3->4->5->NULL, m = 2 and n = 4, return 1->4->3->2->5->NULL. 题中让在一条链表......

Leafage_M ⋅ 2017/10/17 ⋅ 0

数据结构之链表与数组(3):单向链表上的简单操作

原文出处:写代码的李纳 4 反转单向链表(非递归实现) 思路: 图1 非递归反转链表 如图1所示,假设已经反转了前面的若干节点,且前一段链表的头节点指针为pre,则现在要做的事情是首先保存当...

写代码的李纳 ⋅ 2015/11/11 ⋅ 0

菜鸡吃米之链表(未更新完)

链表反转感觉说不出什么算法来,反转就是需要仔细分析各种情况,仔细检查各个部分以避免出现bug就可以了。 下面是两个反转链表的,一个是整体反转,一个是反转第m到n个。 链表问题还有许多其...

跑得比谁都慢 ⋅ 2017/11/13 ⋅ 0

Lintcode36 Reverse Linked List II solution 题解

【题目描述】 Reverse a linked list from position m to n. Notice:Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list. 翻转链表中第m个节点到第n个节点的部分 ......

abcdd1234567890 ⋅ 2017/06/14 ⋅ 0

数据结构基础(9) --单链表的设计与实现(2)之高级操作

链表的链接: 将第二条链表的所有内容链接到第一条链表之后, 其完整实现代码与解析如下: //链表的链接template void MyList::concatenate(const MyList &list){ } 链表的反转: 基本思想: 遍历...

翡青 ⋅ 2015/01/05 ⋅ 0

编程题——11~20

十一、数值的整数次方 实现函数double Power( double base, int exponent ),求base的exponent。不使用哭函数,同时 不需要考虑大数问题。 十二、打印1到最大的n位数 输入数字n,按顺序打印出...

thanatos_y ⋅ 2016/07/21 ⋅ 0

看图理解单链表反转

如何把一个单链表进行反转? 方法1:将单链表储存为数组,然后按照数组的索引逆序进行反转。 方法2:使用3个指针遍历单链表,逐个链接点进行反转。 方法3:从第2个节点到第N个节点,依次逐节...

牧师-Panda ⋅ 2016/10/10 ⋅ 0

算法知识梳理(9) - 链表算法第一部分

面试算法代码知识梳理系列 算法知识梳理(1) - 排序算法 算法知识梳理(2) - 字符串算法第一部分 算法知识梳理(3) - 字符串算法第二部分 算法知识梳理(4) - 数组第一部分 算法知识梳理(5) - 数...

泽毛 ⋅ 2017/12/17 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

容器之重命名镜像

使用docker tag命令来重命名镜像名称,先执行help,查看如何使用如下 mjduan@mjduandeMacBook-Pro:~/Docker % docker tag --helpUsage:docker tag SOURCE_IMAGE[:TAG] TARGET_IMAGE[:TA...

汉斯-冯-拉特 ⋅ 18分钟前 ⋅ 0

with 的高级用法

那么 上下文管理器 又是什么呢? 上下文管理器协议包含 __enter__ 和 __exit__ 两个方法。with 语句开始运行时,会在上下文管理器对象上调用 __enter__ 方法。with 语句运行结束后,会在上下...

阿豪boy ⋅ 38分钟前 ⋅ 0

使用 jsoup 模拟登录 urp 教务系统

需要的 jsoup 相关 jar包:https://www.lanzous.com/i1abckj 1、首先打开教务系统的登录页面,F12 开启浏览器调试,注意一下 Request Headers 一栏的 Cookie 选项,我们一会需要拿这个 Cook...

大灰狼时间 ⋅ 38分钟前 ⋅ 0

关于线程的创建

转自自己的笔记: http://note.youdao.com/noteshare?id=87584d4874acdeaf4aa027bdc9cb7324&sub=B49E8956E145476191C3FD1E4AB40DFA 1.创建线程的方法 Java使用Thread类代表线程,所有的线程对......

MarinJ_Shao ⋅ 49分钟前 ⋅ 0

工厂模式学习

1. 参考资料 工厂模式-伯乐在线 三种工厂-思否 深入理解工厂模式 2. 知识点理解 2.1 java三种工厂 简单工厂 工厂模式 抽象工厂 2.2 异同点 逐级复杂 简单工厂通过构造时传入的标识来生产产品...

liuyan_lc ⋅ 今天 ⋅ 0

Java NIO

1.目录 Java IO的历史 Java NIO之Channel Java NIO之Buffer Java NIO之Selector Java NIO之文件处理 Java NIO之Charset Java 可扩展IO 2.简介 “IO的历史”讲述了Java IO API从开始到现在的发...

士别三日 ⋅ 今天 ⋅ 0

[Err] ORA-24344: success with compilation error

从txt文本复制出创建function的脚本,直接执行,然后报错:[Err] ORA-24344: success with compilation error。 突然发现脚本的关键字,居然不是高亮显示。 然后我把脚本前面的空格去掉,执行...

wenzhizhon ⋅ 今天 ⋅ 0

Spring Security授权过程

前言 本文是接上一章Spring Security认证过程进一步分析Spring Security用户名密码登录授权是如何实现得; 类图 调试过程 使用debug方式启动https://github.com/longfeizheng/logback该项目,...

hutaishi ⋅ 今天 ⋅ 0

HAProxy基于KeepAlived实现Web高可用及动静分离

前言 软件负载均衡一般通过两种方式来实现: 基于操作系统的软负载实现 基于第三方应用的软负载实现 LVS是基于Linux操作系统实现的一种软负载,而HAProxy则是基于第三方应用实现的软负载。 ...

寰宇01 ⋅ 今天 ⋅ 0

微软自研处理器的小动作:已经开始移植其他平台的工具链

微软将 Windows 10 、Linux 以及工具链如 C/C++ 和 .NET Core 运行时库、Visual C++ 2017 命令行工具、RyuJIT 编辑器等移植到其自主研发的处理器架构 E2。微软还移植了广泛使用的 LLVM C/C++...

linux-tao ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部