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.
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* partition(struct ListNode* head, int x) { struct ListNode * l1 = NULL;/*samller than x*/ struct ListNode * l2 = NULL;/*bigger than x*/ struct ListNode * head1 = NULL;/*samller than x*/ struct ListNode * head2 = NULL;/*bigger than x*/ struct ListNode * p = head; if(head == NULL){ return NULL; } while(p){ if(p->val<x){ if(!head1){ head1 = p; }else{ l1->next = p; } l1 = p; }else{ if(!head2){ head2 = p; }else{ l2->next = p; } l2 = p; } p = p->next; } if(head2 != NULL){ l2->next = NULL; } if(head1 != NULL){ l1->next = head2; }else{ head1 = head2; } return head1; } //java solution /** * 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 head1 = null; ListNode l1 = null; ListNode head2 = null; ListNode l2 = null; while(head!=null){ if(head.val<x){ if(head1 == null){ head1 = new ListNode(head.val); l1 = head1; }else{ ListNode node = new ListNode(head.val); l1.next = node; l1 = node; } }else{ if(head2 == null){ head2 = new ListNode(head.val); l2 = head2; }else{ ListNode node = new ListNode(head.val); l2.next = node; l2 = node; } } head = head.next; } if(head1 == null){ return head2; }else{ l1.next = head2; return head1; } } }