问题： 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; }}新闻热点
疑难解答
