文档章节

反转链表

htq
 htq
发布于 2016/07/26 09:41
字数 359
阅读 2
收藏 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
武汉
LeetCode基础算法-链表

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

24K男
09/10
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
面试 8:快慢指针法玩转链表算法面试(二)

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

nanchen2251
07/13
0
0
面试题16:反转链表

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

嗯哼9925
2017/12/21
0
0
143. Reorder List - LeetCode

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

yysue
07/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

记一次winserver2003系统,https无法访问,内存占用持续增加,解决办法

先交代一下环境: win server2003系统,系统装在hyper-v虚拟机里 大概2016年底的镜像,距离今天两年左右 病症:大概9月10号左右用这个镜像还可以访问https,但是今天用这个镜像新装的系统,就...

阳阳露
23分钟前
2
0
jdbc连接orcal数据库

import java.sql.Connection;  import java.sql.DriverManager;  import java.sql.ResultSet;  import java.sql.SQLException;  import java.sql.Statement;    ......

小橙子的曼曼
48分钟前
0
0
Vue学习资料

一直以为Vue是依赖nodejs的。 作为前端也可以耦合性就很低了。 //npm包管理器 进行管理npm install vue//初始化一个项目vue init//本地调试npm run dev//编译完成 ...

大灰狼wow
57分钟前
1
0
fullcalendar重新渲染

uiCalendarConfig.calendars.lesson_calendar.fullCalendar('removeEvents');var ym = uiCalendarConfig.calendars.lesson_calendar.fullCalendar('getView').title;$scope.get_lesson(y......

人来疯啊
今天
1
0
多渠道打包总结

https://www.jianshu.com/p/2130db7584c8 https://blog.csdn.net/u011153817/article/details/50772496...

塔塔米
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部