from : http://hi.baidu.com/fumble/blog/item/b56e5d60029638dc8db10dc4.html
题目:输入一个链表的头结点,反转该链表,并返回反转后链表的头结点。链表结点定义如下:
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
为空指针的结点。
基于上述分析,我们不难写出如下代码:
///////////////////////////////////////////////////////////////////////
// Reverse a list iteratively
// Input: pHead - the head of the original list
// Output: the head of the reversed head
///////////////////////////////////////////////////////////////////////
ListNode* ReverseIteratively(ListNode* pHead)
{
ListNode* pReversedHead = NULL;
ListNode* pNode = pHead;
ListNode* pPrev = NULL;
while
(pNode != NULL)
{
// get the next node, and save it at pNext
ListNode* pNext = pNode->m_pNext;
// if the next node is null, the currect is the end of original
// list, and it's the head of the reversed list
if
(pNext == NULL)
pReversedHead = pNode;
// reverse the linkage between nodes
pNode->m_pNext = pPrev;
// move forward on the the list
pPrev = pNode;
pNode = pNext;
}
return
pReversedHead;
}
扩展:本题也可以递归实现。感兴趣的读者请自己编写递归代码。
分享到:
相关推荐
设计一个将输入数据建立成链表、输出链表数据、利用原空间把链表反转的程序代码。
基于linkedList实现自己的双向链表反转。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。...
链表反转程序C++ 运行良好,简单,高效,实用的程序
链表反转 在VC++6.0下运行成功 程序
本资料实例讲解java单项链表的实现以及拓展进行排序,每行代码都附有注释
c++链表的反转,创建链表,插入链表,链表反转,可下载直接运行。
链表反转
①链表反转 单向链表的反转是一个经常被问到的一个面试题,也是一个非常基础的问题。比如一个链表是这样的: 1->2->3->4->5 通过反转后成为5->4->3->2->1。 最容易想到的方法遍历一遍链表,利用一个辅助指针,存储...
单链表基本操作 基于Java实现的单链表基本操作之链表反转
用C++编写的将链表反转的源程序,可以运行,简单易懂。
本文实例讲述了Python实现链表反转的方法。分享给大家供大家参考,具体如下: Python实现链表反转 链表反转(while迭代实现): 链表的反转引入一个cur_node变量,表示当前节点;同时需要引入一个变量new_link表示...
K个一组的链表反转
链表反转将单链表的链接顺序反转过来例如:输入:1->2->3->4->5输出:5->4->3->2->1使用两种方式解题* @return 返回倒序后的链表头部
206. 链表反转206. 反转链表 — Easy题目描述示例:解题思路头插法,每次从原链表的头部取下一个节点,利用头插法将其插入新链表的头部图不应该这么画,h
C语言数据结构 link 链表反转的实现 链表反转,示例如下: 偶数个输入:a->b->c->d->e->f 偶数个输出:e->f->c->d->a->b or 奇数个输入:a->b->c->d->e->f->g 偶数个输出:g->e->f->c->d->a->b #include #...
想要写好链表代码并不是容易的事儿,尤其是那些复杂的链表操作,比如链表反转、有序链表合并等,写的时候非常容易出错。比如说,如果你真的能花上一个周末或者一整天的时间
单向链表的反转是一个经常被问到的一个面试题,也是一个非常基础的问题。比 如一个链表是这样的: 1->2->3->4->5 通过反转后成为5->4->3->2->1。 最容易想到的方法遍历一遍链表,利用一个辅助指针,存储遍历过程中...
主要为大家详细介绍了Java实现单向链表反转,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
通过java实现的双向链表,及反转功能,可能对面试有用哦