My code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode partition(ListNode head, int x) {
if (head == null)
return null;
else if (head.next == null)
return head;
ListNode dummy = new ListNode(Integer.MIN_VALUE);
dummy.next = head;
int total = 0;
ListNode temp = dummy;
ListNode tail = null;
while (temp.next != null) {
temp = temp.next;
total++;
}
tail = temp;
ListNode preInsert = dummy;
temp = dummy.next;
int counter = 0;
while (counter < total) {
if (temp.val >= x) {
if (temp.next == null)
break;
preInsert.next = temp.next;
tail.next = temp;
temp.next = null;
tail = temp;
temp = preInsert.next;
}
else {
preInsert = temp;
temp = preInsert.next;
}
counter++;
}
return dummy.next;
}
}
My test result:
这道题目类似于快排链表的一个小操作，换结点。
但是这比插入排序链表要爽多了。。。
因为我这里总是在尾部插入，可以省掉许多考虑。。
早晨起来觉得拖着也是拖着，就把一家公司的网上笔试做了。
20道题目，35分钟。感觉很奇怪。。。不难，但又不简单，或者说，就是智商题吧。。
不知道做的怎么样。也没底。感觉不差，也不好。
9.30微软面试，我得好好准备下了。
想把之前写的文章全部重看一遍。然后基础的排序什么的，必须搞清楚。
今天一定要把CG搞定！！！
感觉写的还是很复杂，实在不能理解，为什么要统计数字。是怕把tail后面的也重复遍历进去吗？
我的简化代码如下：
public ListNode partition(ListNode head, int x) {
if (head == null)
return null;
else if (head.next == null)
return head;
ListNode dummy = new ListNode(Integer.MIN_VALUE);
dummy.next = head;
ListNode tail = head;
while (tail.next != null)
tail = tail.next;
ListNode insertTail = tail;
ListNode pre = dummy;
ListNode curr = pre.next;
while (curr != tail) {
if (curr.val >= x) {
pre.next = curr.next;
curr.next = null;
insertTail.next = curr;
insertTail = curr;
curr = pre.next;
}
else {
pre = curr;
curr = pre.next;
}
}
if (curr.val >= x) {
if (curr.next == null)
return dummy.next;
pre.next = curr.next;
curr.next = null;
insertTail.next = curr;
}
return dummy.next;
}
的确需要注意的是，不要把tail后面的也给扫描进去了。
所以，到tail为止，结束循环。然后单独处理tail就可以了。
不写了。明天面试。回去复习下简历，问答。
好运！！！
**
总结： 快排链表
**
Anyway, Good luck, Richardo!
My code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode partition(ListNode head, int x) {
if (head == null || head.next == null)
return head;
ListNode tail = head;
int counter = 1;
/** get the tail node of this linked list */
while (tail.next != null) {
counter++;
tail = tail.next;
}
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy;
ListNode curr = head;
int i = 0;
while (i < counter) {
if (curr.val < x) {
pre = pre.next;
curr = curr.next;
}
else {
if (curr == tail)
break;
pre.next = curr.next;
curr.next = null;
tail.next = curr;
tail = curr;
curr = pre.next;
}
i++;
}
return dummy.next;
}
}
这次写的感觉比以前简单一些。。
然后我的思路，和刚刚有道题目的第二种解法一样。
- Odd Even Linked List
http://www.jianshu.com/p/c4a424042667
这道题木，第二种解法，就是扫描链表。碰到偶数的，就把他直接插到链表后部。
这道题木也一样。碰到 >= x的，直接把他插到链表后部。
刚刚那道题目，采用了一个ListNode endTag来防止重复扫描的问题，即把tail后面，后来插入的结点也给扫描了。
这道题木我换了一种做法。直接做一个计数器记录结点总个数。
然后while循环就用这个做判断。会简单很多。
当然，这道题木，需要判断 curr == tail
如果等于的话，我的当前代码是不能把curr 插入到自己后面的。直接break就行。
这个错误，也犯过好几次。就是自己对自己进行处理。处理不了，出错。以后要注意。
Anyway, Good luck, Richardo!
My code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode partition(ListNode head, int x) {
if (head == null || head.next == null) {
return head;
}
ListNode smallHead = new ListNode(-1);
ListNode bigHead = new ListNode(-1);
ListNode small = smallHead;
ListNode big = bigHead;
while (head != null) {
if (head.val < x) {
small.next = head;
small = small.next;
}
else {
big.next = head;
big = big.next;
}
head = head.next;
}
small.next = bigHead.next;
big.next = null;
return smallHead.next;
}
public static void main(String[] args) {
Solution test = new Solution();
ListNode n1 = new ListNode(2);
ListNode n2 = new ListNode(1);
n1.next = n2;
test.partition(n1, 2);
}
}
我的做法挺复杂，也没做出来。最后估计可以debug出来，但corner case 太多。
这个做法比较简洁易懂，关注点在于：
big.next = null; 必须切断。否则就是一个环，无限循环。
reference:
https://discuss.leetcode.com/topic/7005/very-concise-one-pass-solution/5
特点在于，用了双dummy node
然后想到 odd even linked list 应该也可以这么做
http://www.jianshu.com/p/c4a424042667
Anyway, Good luck, Richardo! --- 08/17/2016
