問題： Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should PReserve the original relative order of the nodes in each of the two partitions.
For example, Given 1->4->3->2->5->2 and x = 3, return 1->2->2->4->3->5.
這個問題的思路是：輪尋整個鏈表，將大于等于x的node移到另一個鏈表中。 然后，合并兩個鏈表即可。
代碼示例：
/** * 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) { //tmp用于輪尋原始鏈表 ListNode tmp = head; //prev用于記錄tmp之前的節點 ListNode prev = null; //otherHead用于記錄另一個鏈表的頭節點 ListNode otherHead = null; //other用于輪尋另一個鏈表 ListNode other = null; while (tmp != null) { //小于x的節點直接跳過 while (tmp != null && tmp.val < x) { prev = tmp; tmp = tmp.next; } //否則將tmp從原始鏈表中移除 if (tmp != null) { if (prev != null) { prev.next = tmp.next; } else { head = tmp.next; } } //將tmp加入到另一個鏈表中 if (other == null) { otherHead = tmp; other = tmp; } else { other.next = tmp; other = other.next; } //繼續移動tmp if (tmp != null) { tmp = tmp.next; } } //合并兩個鏈表 if (prev != null) { prev.next = otherHead; } else { //這里是原始鏈表中，所有的值都大于等于x的情況 head = otherHead; } return head; }}新聞熱點
疑難解答
