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->5
Solutions:
/**
Definition for singly-linked list.
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
*/
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode Fakehead1 = new ListNode(0), Fakehead2 = new ListNode(0);
ListNode low = Fakehead1;
ListNode high = Fakehead2;
while (head != null)
{
if (head.val < x)
{
low.next = head;
low = head;
}
else
{
high.next = head;
high = head;
}
head = head.next;
}
high.next = null;
low.next = Fakehead2.next;
return Fakehead1.next;
}
}
Points:
My original though contained the low and high lists idea. We optimized the solution here to give them two Fakeheads and to compare the moving head each time with the moving low and high lists.
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->5
Solutions: /**
Points: