LeetCode 86: Partition List

LeetCode Linked 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.

代码

C语言版本：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* partition(struct ListNode* head, int x) {
    if ( !head ) {
        return NULL;
    }
    struct ListNode *smaller, *smallerHeader;
    smallerHeader -> next = head;
    smaller = smallerHeader;
    struct ListNode *bigger, *biggerHeader;
    biggerHeader -> next = head;
    bigger = biggerHeader;
    while ( head ) {
        if ( head -> val < x ) {
            smaller -> next = head;
            smaller = head;
        }else {
            bigger -> next = head;
            bigger = head;
        }
        head = head -> next;
    }
    bigger -> next = NULL;
    smaller -> next = biggerHeader -> next;
    return smallerHeader -> next;
}

166 / 166 test cases passed.
Status: Accepted
Runtime: 4 ms