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搞定！：锩洹阴幌！
感覺寫的還是很復雜，實在不能理解卷中，為什么要統(tǒng)計數字矛双。是怕把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為止十减，結束循環(huán)栈幸。然后單獨處理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.reibang.com/p/c4a424042667
這道題木，第二種解法壹若，就是掃描鏈表嗅钻。碰到偶數的，就把他直接插到鏈表后部店展。
這道題木也一樣养篓。碰到 >= x的，直接把他插到鏈表后部赂蕴。
剛剛那道題目柳弄，采用了一個ListNode endTag來防止重復掃描的問題，即把tail后面概说，后來插入的結點也給掃描了碧注。
這道題木我換了一種做法。直接做一個計數器記錄結點總個數糖赔。
然后while循環(huán)就用這個做判斷萍丐。會簡單很多。
當然放典，這道題木逝变，需要判斷 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; 必須切斷假抄。否則就是一個環(huán)，無限循環(huán)。
reference:
https://discuss.leetcode.com/topic/7005/very-concise-one-pass-solution/5
特點在于宿饱，用了雙dummy node
然后想到 odd even linked list 應該也可以這么做
http://www.reibang.com/p/c4a424042667
Anyway, Good luck, Richardo! --- 08/17/2016
