[LeetCode 86]Partition List

题目链接：partition-list

/** * 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.Hide Tags * */public class PartitionList {public class ListNode {int val;ListNode next;ListNode(int x) {val = x;next = null;}}//166 / 166 test cases passed.//Status: Accepted//Runtime: 288 ms//Submitted: 1 minute ago//设置两个链表，，小于x的节点按顺序链接到less尾部中，大于或等于的节点按顺序链接到greater尾部//时间复杂度o(n),空间复杂度 o(1)public ListNode partition(ListNode head, int x) {ListNode less = new ListNode(Integer.MAX_VALUE);ListNode greater = new ListNode(Integer.MAX_VALUE);ListNode cur1 = less;ListNode cur2 = greater;while(head != null) {if(head.val < x) {cur1.next = head;cur1 = cur1.next;} else {cur2.next = head;cur2 = cur2.next;}head = head.next;}cur2.next = null;cur1.next = greater.next;return less.next;}public static void main(String[] args) {// TODO Auto-generated method stub}}

为了一些琐事吵架，然后冷战，疯狂思念对方，最后和好。