文档章节

反转链表

htq
 htq
发布于 2016/07/26 09:41
字数 359
阅读 3
收藏 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

共有 人打赏支持
下一篇: javaRMI详解
htq

htq

粉丝 19
博文 67
码字总数 1007
作品 3
武汉
私信 提问
剑指offer 16. 反转链表

原题 输入一个链表,反转链表后,输出新链表的表头。 Reference Answer 解题思路: 对于这种python求解链表题,尤其是本题让返回节点或者值,直接先遍历玩链表转换到 python 的list中,再进行...

dby_freedom
10/20
0
0
LeetCode基础算法-链表

# LeetCode基础算法-链表 LeetCode 链表 1. 删除链表中的节点 请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点,你将只被给定要求被删除的节点。 解题思路: 使用赋值取代法来实...

24K男
09/10
0
0
面试 8:快慢指针法玩转链表算法面试(二)

昨天在最后给大家留了拓展题,不知道大家有没有思考完成,其实南尘说有巨坑是吓大家的啦,实际上也没什么。我们来继续看看昨天这个拓展题。 面试题:给定单链表的头结点,删除单链表的倒数第...

nanchen2251
07/13
0
0
反转单链表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
1
0
143. Reorder List - LeetCode

Question 143. Reorder List Solution 题目大意:给一个链表,将这个列表分成前后两部分,后半部分反转,再将这两分链表的节点交替连接成一个新的链表 思路 :先将链表分成前后两部分,将后部...

yysue
07/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Supplier函数式接口

Supplier接口的不传入参数,返回一个值。真是一个无私奉献的接口,还没有default方法。 下面就想用一个接口试试,其实我本来用的是IntSupplier,但是发现在使用方法引用的时候,不好把Math....

woshixin
12分钟前
0
0
MyBaties一级缓存

一、一级缓存简介 在系统代码的运行中,我们可能会在一个数据库会话中,执行多次查询条件完全相同的Sql,鉴于日常应用的大部分场景都是读多写少,这重复的查询会带来一定的网络开销,同时sel...

嘴角轻扬30
19分钟前
0
0
jquery

语法 描述 实例 $("*") 选取所有元素 在线实例 $(this) 选取当前 HTML 元素 在线实例 $("p.intro") 选取 class 为 intro 的 <p> 元素 在线实例 $("p:first") 选取第一个 <p> 元素 在线实例 ...

mskk
24分钟前
1
0
微信红包设计方案

前言 微信红包一经推出,春节期间微信用户红包总发送量达80.8亿,红包峰值40.9w/秒,在如此量级下,系统设计存在各种变数,稍有闪失会功亏一篑。 红包系统 红包系统有三部分组成:信息流,业...

春哥大魔王的博客
34分钟前
1
0
微信开发-正式号的配置

1、设置相关 业务域名的设置(不设置的话,相关页面会显示防欺诈盗号信息提示) JS接口安全域名设置 网页授权域名设置 注意:以上三个设置中都有下载文件的提示,此文件内容一样,下载一个即可...

Code辉
39分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部