https://leetcode.com/problems/partition-list/
https://leetcode.com/articles/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.
Example:
Input: head = 1->4->3->2->5->2, x = 3 Output: 1->2->2->4->3->5https://leetcode.com/problems/partition-list/discuss/29183/Concise-java-code-with-explanation-one-pass
the basic idea is to maintain two queues, the first one stores all nodes with val less than x , and the second queue stores all the rest nodes. Then concat these two queues. Remember to set the tail of second queue a null next, or u will get TLE.
I think it is not the cycled linked list that cause the TLE. at the end of your loop. curr2 point to the last element but does not have the next pointer...so I think it maybe the checking standards do not know if it is an end or not.
public ListNode partition(ListNode head, int x) {
ListNode dummy1 = new ListNode(0), dummy2 = new ListNode(0); //dummy heads of the 1st and 2nd queues
ListNode curr1 = dummy1, curr2 = dummy2; //current tails of the two queues;
while (head!=null){
if (head.val<x) {
curr1.next = head;
curr1 = head;
}else {
curr2.next = head;
curr2 = head;
}
head = head.next;
}
curr2.next = null; //important! avoid cycle in linked list. otherwise u will get TLE.
curr1.next = dummy2.next;
return dummy1.next;
}https://leetcode.com/articles/partition-list/
public ListNode partition(ListNode head, int x) {
// before and after are the two pointers used to create the two list
// before_head and after_head are used to save the heads of the two lists.
// All of these are initialized with the dummy nodes created.
ListNode before_head = new ListNode(0);
ListNode before = before_head;
ListNode after_head = new ListNode(0);
ListNode after = after_head;
while (head != null) {
// If the original list node is lesser than the given x,
// assign it to the before list.
if (head.val < x) {
before.next = head;
before = before.next;
} else {
// If the original list node is greater or equal to the given x,
// assign it to the after list.
after.next = head;
after = after.next;
}
// move ahead in the original list
head = head.next;
}
// Last node of "after" list would also be ending node of the reformed list
after.next = null;
// Once all the nodes are correctly assigned to the two lists,
// combine them to form a single list which would be returned.
before.next = after_head.next;
return before_head.next;
}
