86. Partition List

86. Partition List:题目链接

基本思想:在遍历head的同时，创建两个链表，(dummy_1)用来存放小于x的节点，(dummy_2)用来存放大于等于x的节点，最后将dummy_2的最后一个节点指针域置为NULL，被链接到dummy_1的最后一个节点

// 时间复杂度O(N)  空间复杂度O(1)
struct ListNode *partition(struct ListNode *head, int x) {
    LinkNode *dummy_1 = (LinkNode *) malloc(sizeof(LinkNode));      // 设立带头结点的链表 存放小于x的节点
    LinkNode *dummy_2 = (LinkNode *) malloc(sizeof(LinkNode));      // 设立带头结点的链表 存放大于等于x的节点
    LinkNode *curNode_1 = dummy_1, *curNode_2 = dummy_2;
    while (head) {
        if (head->val < x) {
            curNode_1->next = head;
            curNode_1 = head;
        } else {
            curNode_2->next = head;
            curNode_2 = head;
        }
        head = head->next;
    }
    curNode_2->next = NULL;           // dummy_2要接在dummy_1的后面，当然要将整体的最后一个元素的指针域置为NULL
    curNode_1->next = dummy_2->next;
    return dummy_1->next;
}

pS: 源代码链接