原题链接:http://oj.leetcode.com/problems/partition-list/这是一道链表操作的题目,要求把小于x的元素按顺序放到链表前面。我们仍然是使用链表最常用的双指针大法,一个指向当前小于x的最后一个元素,一个进行往前扫描。如果元素大于x,那么继续前进,否则,要把元素移到前面,并更新第一个指针。这里有一个小细节,就是如果不需要移动(也就是已经是接在小于x的最后元素的后面了),那么只需要继续前进即可。算法时间复杂度是O(n),空间只需要几个辅助变量,是O(1)。代码如下:public ListNode partition(ListNode head, int x) {
if(head == null)
return null;
ListNode helper = new ListNode(0);
helper.next = head;
ListNode walker = helper;
ListNode runner = helper;
while(runner.next!=null)
{
if(runner.next.val<x)
{
if(walker!=runner)
{
ListNode next = runner.next.next;
runner.next.next = walker.next;
walker.next = runner.next;
runner.next = next;
}
else
runner = runner.next;
walker = walker.next;
}
else
{
runner = runner.next;
}
}
return helper.next;
}
这道题思路比较清晰,不过还是有点细节的,第一次写可能不容易完全写对,可以练习练习。
分享到:
相关推荐
leetcode lintcode差异 leetcode-python 九章算法基础班 二分 题目 地址 153. Find ...List) LintCode 373. Partition Array by Odd and Even Mock Interview 题目 Solution Tag Dynamic Programming
leetcode安卓 Leetcode 1. Dynamic Programming When to use: 之后的结果对前面没有影响,并且存在关系 F(n)=f(F(k<...解决dp问题关键是找到推进公式 ...Partition每个元素往前看,重新分区: (Simi
partition-list 92 反转链表 II reverse-linked-list-ii(Reverse a Sub-list) 141 环形链表 linked-list-cycle 142 环形链表 II linked-list-cycle-ii 143 重排链表 reorder-list 148 排序链表 sort-list 234 回文...
A Partition-Based Approach to Structure Similarity Search A Partition-Based Approach to Structure Similarity Search
对Partition-Guided GANs进行了翻译和注释
leetcode 跳跃 leetcode刷题笔记 005-2. 最长回文子串 字符串+中心扩散 ...分治+递归+快排的partition思想 217-1. 存在重复元素 数组+排序 230-2. 二叉搜索树中第K小的元素 二叉搜索树+递归+剪枝 231-1.
* [Linked List](https://github.com/kamyu104/LeetCode#linked-list) * [Stack](https://github.com/kamyu104/LeetCode#stack) * [Queue](https://github.com/kamyu104/LeetCode#queue) * [Heap]...
86.Partition List LeetCode 92.Reverse Linked List II LeetCode 138.Copy List with Random Pointer LeetCode 142.Linked List Cycle II(solve1) LeetCode 142.Linked List Cycle II(solve2) LeetCode 160....
Introduce the way to partition large SQL Table.
Partition I* 66.3% 766 Toeplitz Matrix 57.7% 566 Reshape the Matrix* 57.7% 485 Max Consecutive Ones* 53.7% 695 Max Area of Island* (DFS) 51.8% 283 Move Zeroes* 51.5% 448 Find All Numbers Disappeared ...
Partition Equal Subset Sum 最长回文:5. Longest Palindromic Substring - 字数组余数:523. Continuous Subarray Sum - 无重复字符的最长子串:3. Longest Substring Without Repeating Characters - 最小跳跃步...
list , Reference: Stack , Reference: , , Heap , Tree , , , DP/Greedy Reference: Reference: , Reference: , , , , , Recurrence Reference: Important NOTE!: 其中的Partition 是很常见的operation,标准做法是...
构建大顶堆leetcode 暖身 注意注意 // n = Integer.MIN_VALUE; n = -n; 快排 private int partition(int[] nums, int left, int right) { int tmp = nums[left]; while(left < right) { while(left<right>=tmp) {...
1.ArrayPartition数组划分: 给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ,使得从1 到 n 的 min(ai, bi) 总和最大。 2.TwoSum两数之和: 给定一个整数数组和一个...
因为荷兰国旗问题中间是一堆数确定了位置,而普通的partition只确定了一个位置。 自己写一下二叉树的寻找后继节点问题(前驱节点也就类似)。 在初级5 70分钟 怎么判断一颗树是否是完全二叉树。 要用层次遍历来,...
var iterator = require ( 'partition-refinement-iterator' ) ; var iterate = iterator ( Number ( process . argv [ 2 ] ) ) ; while ( true ) { var n = iterate ( ) ; if ( typeof n == 'undefined' ) break ...
minitool-partition-wizard的11版本,目前应该到12了,这个11是我之前下载的版本,测试过可以完全使用,我用该工具主要是用来将window系统镜像到新的硬盘里面去,这个工具有个好处是不管新的磁盘是否比旧的磁盘容量...
mysql表分区的建立,索引的建立,原理说明,还有就是实例的演示
leetcode 不会 Most problem set in interviews are testing your basic knowledge. DO NOT underestimate the importance of basics. Problems about Array To begin with, a simple question: 283 To minimize ...
partition-bundle, 在不同的包中,用于划分模块的browserify插件 分区捆绑包一个 browserify插件插件将多个相关模块打包在一起,以使最初的更小。npm install partition-bundle示例browserify -p [ partition-bundl