你的位置:首页 > 软件开发 > ASP.net > 单链表倒置

单链表倒置

发布时间:2015-05-18 12:01:20
我想你去很多家公司面试的时候,遇到单链表倒置的问题可能比较多,如果一定要给面试题来一个排名,估计也能上top10吧,其实这个题目玩的是技巧和你对单链表的理解,其实我们仔细想想也不是很难,既然是倒置,那我们一定是一定要走一遍单链表的,对吧,那么走单链表有两种形式,递归和循环两种方式 ...

 我想你去很多家公司面试的时候,遇到单链表倒置的问题可能比较多,如果一定要给面试题来一个排名,估计也能上top10吧,其实这个

题目玩的是技巧和你对单链表的理解,其实我们仔细想想也不是很难,既然是倒置,那我们一定是一定要走一遍单链表的,对吧,那么走单链

表有两种形式,递归和循环两种方式,而递归正是压栈和出栈,那么我们就想起来了,这不就是顺序和逆序的关系吗?第二种就是循环,还记

得我们曾今学习单链表的时候有一种插法叫做头插法,这种插入复杂度为O(1),不好的地方就是顺序插入的数字,出来的时候却是反的,所以这

个不就是可以将原先的链表原地倒置过来吗?

 

一:递归

  说到递归,我们脑子里面一定要有一个V型图,还有一个就是好记性不如烂笔头,算法这东西很难用脑子想的清楚的,多画画图就见青天了,

下面我就举个简单的例子:现有链表L={8,1,6,3},需要将L倒置,然后我就画好了V型图。

单链表倒置

从图中可以看到,当我递归到3再出栈的时候,只需要将6赋给3.next,1赋给6.next,然后这样以此类推。。。最后结果就出来了,貌似

口头上描述起来很简单,但是在写代码的时候需要注意以下几个点,先上代码说话。

单链表倒置
 1     public LinkNode Reserve(LinkNode node) 2     { 3       LinkNode prev = null; 4       LinkNode next = null; 5 6       while (node != null) 7       { 8         next = node.next; 9 10         node.next = prev;11 12         prev = node;13 14         node = next;15       }16       return prev;17     }
单链表倒置

 

其实我们发现,代码只有那么一点点,但是信息量还是蛮大的,这些东西要是用口头描述还是很累的。

 


原标题:单链表倒置

关键词:

*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们: admin#shaoqun.com (#换成@)。

可能感兴趣文章

我的浏览记录