链表结点定义如下:
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
分析:这是一道广为流传的微软面试题。由于这道题能够很好的反应出程序员思维是否严密,在微软之后已经有很多公司在面试时采用了这道题。
为了正确地反转一个链表,需要调整指针的指向。与指针操作相关代码总是容易出错的,因此最好在动手写程序之前作全面的分析。在面试的时候不急于动手而是一开始做仔细的分析和设计,将会给面试官留下很好的印象,因为在实际的软件开发中,设计的时间总是比写代码的时间长。与其很快地写出一段漏洞百出的代码,远不如用较多的时间写出一段健壮的代码。
为了将调整指针这个复杂的过程分析清楚,我们可以借助图形来直观地分析。假设下图中l、m和n是三个相邻的结点:
a?b?…?l
mànà…
假设经过若干操作,我们已经把结点l之前的指针调整完毕,这些结点的m_pNext指针都指向前面一个结点。现在我们遍历到结点m。当然,我们需要把调整结点的m_pNext指针让它指向结点l。但注意一旦调整了指针的指向,链表就断开了,如下图所示:
a?b?…l?m
nà…
因为已经没有指针指向结点n,我们没有办法再遍历到结点n了。因此为了避免链表断开,我们需要在调整m的m_pNext之前要把n保存下来。
接下来我们试着找到反转后链表的头结点。不难分析出反转后链表的头结点是原始链表的尾位结点。什么结点是尾结点?就是m_pNext为空指针的结点。
基于上述分析,我们不难写出如下代码:
扩展:本题也可以递归实现。感兴趣的读者请自己编写递归代码。
分享到:
相关推荐
设计一个将输入数据建立成链表、输出链表数据、利用原空间把链表反转的程序代码。
c++链表的反转,创建链表,插入链表,链表反转,可下载直接运行。
反转链表 迭代法## 逐个节点反转## 更新指针位置## 返回反转后的头结点反转 a 到 b 之间的结点反转区间 [a, b) 的元素,注意是左闭右开K 个一组
键盘输入一组元素,建立一个无头结点的单向链表(无序)。 (2).遍历(打印)单向链表。 (3).把单向链表中元素逆置(不允许申请新的结点空间)。 (4).在单向链表中删除所有的偶数元素结点。 (5).对链表排序,排序...
用C++编写的将链表反转的源程序,可以运行,简单易懂。
①链表反转 单向链表的反转是一个经常被问到的一个面试题,也是一个非常基础的问题。比如一个链表是这样的: 1->2->3->4->5 通过反转后成为5->4->3->2->1。 最容易想到的方法遍历一遍链表,利用一个辅助指针,存储...
输入一个链表,输出该链表中倒数第k个结点。 分析 方法一:先计数,在查询,相当于遍历两遍。 方法二:将所有值存到一个list里,只遍历一遍。 方法三:两个指针都指向头结点,一个指针先走k-1个节点,然后两个指针...
基于linkedList实现自己的双向链表反转。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。...
本资料实例讲解java单项链表的实现以及拓展进行排序,每行代码都附有注释
定义一个5个节点的单链表,然后通过指针的移动调换链表节点的顺序,从而实现链表的反转
反转链表,记录了详细的题目解析思路以及Java语言的参考代码。 适合人群:学习算法和数据结构的程序员或学生,尤其是想系统学习链表操作的人。 能学到什么:掌握链表虚拟头节点设置方法;练习链表基本操作函数如增删...
LeetCode 206的题目是“反转链表”(Reverse Linked List),它要求将一个单链表的所有节点反转,并返回反转后链表的头节点。这是一个基础但非常重要的链表操作问题,它不仅考察了对链表数据结构的理解,还涉及到了...
用迭代、递归、头插、就地逆置共 4 种方法反转带头节点的链表,代码用 C 语言实现。
链表反转 在VC++6.0下运行成功 程序
在一个二位数组中,每一行都按照从左到右 递增的顺序排序,每一列都按照从上到下递增的顺 序排序。输入一个链表的头结点,从尾到头反过来打 ...:定义一个函数,输入一个链表的头结点,反转该链表并输出反转后链表
链表反转程序C++ 运行良好,简单,高效,实用的程序
链表的反转是一个很常见、很基础的数据结构题,输入一个单向链表,输出逆序反转后的链表,如图:上面的链表转换成下面的链表。实现链表反转有两种方式,一种是循环迭代,另外一种方式是递归。 第一种方式:循坏...
本代码,实现了基本的链表结构,同时完成了链表的翻转操作。链表的翻转是IT程序员面试时的常见问题,对找工作的同学,进一步了解链表的性能,有很大的帮助。
单向链表的反转是一个经常被问到的一个面试题,也是一个非常基础的问题。比 如一个链表是这样的: 1->2->3->4->5 通过反转后成为5->4->3->2->1。 最容易想到的方法遍历一遍链表,利用一个辅助指针,存储遍历过程中...
015-反转链表题目描述输入一个链表,反转链表后,输出新链表的表头。思路从原链表的头部一个一个取节点并插入到新链表的头部。指针tmp指向还没进行反转的原链表头部