原题链接:http://oj.leetcode.com/problems/reorder-list/这是一道比较综合的链表操作的题目,要按照题目要求给链表重新连接成要求的结果。其实理清思路也比较简单,分三步完成:(1)将链表切成两半,也就是找到中点,然后截成两条链表;(2)将后面一条链表进行reverse操作,就是反转过来;(3)将两条链表按顺序依次merge起来。这几个操作都是我们曾经接触过的操作了,第一步找中点就是用Linked
List Cycle中的walker-runner方法,一个两倍速跑,一个一倍速跑,知道快的碰到链表尾部,慢的就正好停在中点了。第二步是比较常见的reverse操作,在Reverse
Nodes in k-Group也有用到了,一般就是一个个的翻转过来即可。第三步是一个merge操作,做法类似于Sort
List中的merge,只是这里不需要比较元素打小了,只要按顺序左边取一个,右边取一个就可以了。接下来看看时间复杂度,第一步扫描链表一遍,是O(n),第二步对半条链表做一次反转,也是O(n),第三部对两条半链表进行合并,也是一遍O(n)。所以总的时间复杂度还是O(n),由于过程中没有用到额外空间,所以空间复杂度O(1)。代码如下:public void reorderList(ListNode head) {
if(head == null || head.next==null)
{
return;
}
ListNode walker = head;
ListNode runner = head;
while(runner.next!=null && runner.next.next!=null)
{
walker = walker.next;
runner = runner.next.next;
}
ListNode head1 = head;
ListNode head2 = walker.next;
walker.next = null;
head2 = reverse(head2);
while(head1!=null && head2!=null)
{
ListNode next = head2.next;
head2.next = head1.next;
head1.next = head2;
head1 = head2.next;
head2 = next;
}
}
private ListNode reverse(ListNode head)
{
ListNode pre = null;
ListNode cur = head;
while(cur!=null)
{
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
这道题看起来比较复杂,其实理清思路之后就都是链表常见的几个基本操作。这里我想多说一下reverse操作,因为这是链表最常见的操作。有时候在第一轮电面这种比较基础的面试中,可能会要求实现reverse操作,但是因为有点过于简单,面试官会要求递归和非递归都实现一下。上面的代码使用非递归的方式实现reverse。下面我们列举一下递归的代码,有兴趣的朋友可以看看哈。public ListNode recursive_reverse(ListNode head) {
if(head == null || head.next==null)
return head;
return recursive_reverse(head, head.next);
}
private ListNode recursive_reverse(ListNode current, ListNode next)
{
if (next == null) return current;
ListNode newHead = recursive_reverse(current.next, next.next);
next.next = current;
current.next = null;
return newHead;
}
分享到:
相关推荐
BootStrapTable行内编辑;压缩包内包含行内编辑所需要的js+css; BootStrapTable行内编辑;压缩包内包含行内编辑所需要的js+css;
bootstrap-table实现 行拖拽 插件 jquery.tablednd.js bootstrap-table-reorder-rows.js bootstrap-table-reorder-rows.css
bootstrap-table-reorder-columns表格拖拽排序列的一个插件
bootstrap-table-reorder-rows.js ,bootstraptable行拖动
leetcode中325题python leetcode 以 参考 和 Hash相关 1_两数之和 387_字符串中的第一个唯一字符 链表操作 ...reorder-list 148 排序链表 sort-list 234 回文链表 palindrome-linked-list 双指针遍历/滑动
pip install reorder-python-imports 控制台脚本 有关完整的选项集,请参阅reorder-python-imports --help 。 reorder-python-imports将文件名作为位置参数 常用选项: --py##-plus :。 --add-import / --...
Given a singly linked list$ L: L_0→L_1→…→L{n-1}→L_n$, reorder it to: $L_0→L_n →L_1→L_{n-1}→L_2→L_{n-2}→…$ You must do this in-place without altering the nodes' values. For example, Given...
* [Linked List](https://github.com/kamyu104/LeetCode#linked-list) * [Stack](https://github.com/kamyu104/LeetCode#stack) * [Queue](https://github.com/kamyu104/LeetCode#queue) * [Heap]...
介绍了Ajax控件-ReorderList的使用方法:添加数据,修改数据,删除数据,以及拖动排序。除了修改数据有部分代码,其他功能皆无代码(ReorderList的界面拖动排序也无需代码),都是一次性绑定数据源控件。~~还在为网络...
preorder-traversal链表reorder-list链表linked-list-cycle-ii链表linked-list-cycle动态规划word-break-ii动态规划word-break链表copy-list-with-random-pointer复杂度single-number-ii复杂度single-number动态规划
ASP.NET AJAX的ReorderList控件是可以实现无排序数据绑定的列表控件,从名字上就可以看出来因为它是Reorder的,也就是说能够通过和服务器端交互数据重新排序绑定的数据项。要实现重排序,用户只需简单的拖动某条记录的...
通过工具栏按钮(或键盘快捷键)将活动选项卡移动到左侧或右侧。 标签重新排序是一个扩展,可以...注意:为了报告错误,请在插件主页(http://mybrowseraddon.com/tab-reorder.html)填写错误报告表。 支持语言:English
语言:English 在Windows / Mac上使用Ctrl-Shift PGUP / PGDN重新排序快捷方式,就像您在Linux中一样。 是新的?此扩展名不需要执行此扩展名。关于Chrome上Linux允许您使用键盘快捷键Ctrl-Shift-PGUP和Ctrl-Shift-...
关于React Reorder是一个React组件,允许用户拖放列表(水平/垂直)或网格中的项目。 它完全支持触摸设备并在拖动组件时自动滚动(请查看演示,下面的链接)。 它还允许用户设置保持时间(拖动开始之前的持续时间)...
管理shell脚本,如果主服务器已关闭,则可以重新排序/etc/resolv.conf中的名称服务器条目,从而无需等待超时即可退回到辅助服务器,从而可以更快地进行dns查找。
这是我面试的一家公司的实实在在的项目。版本1.3变化: 新增了将问题添加到类别的功能新增了从类别中删除问题的功能类别现在显示标题中的问题数量版本1.2 版本1.1 版本1.0 yarn start 在开发模式下运行应用程序。...
实现bootStarp Table 表格行拖拽所需js, table属性 onReorderRowsDrag: function(table, row) { //取索引号 dragbeforeidx = $(row).attr("data-index"); }, //拖拽完成后的这条数据,并且可以获取这行数据的...
重新排序孩子 关于 添加通过拖放重新排序特定页面的子项的功能。 在 Radiant 1.0.0.rc2 上测试过,但应该适用于旧版本。 此扩展基于 John Long 为准备该功能成为 ... config.gem "radiant-reorder_children-extens