题解 | #划分链表#

题解一：创建两个节点分别指向大于x和小于x
图示：

复杂度分析：
时间复杂度：O(n)
空间复杂度：O(1)
实现如下：

class Solution {
public:
    /**
     *
     * @param head ListNode类
     * @param x int整型
     * @return ListNode类
     */
    ListNode* partition(ListNode* head, int x) {
    if(head == NULL ||head->next ==NULL) return head;   //为空或者只有一个节点
    struct ListNode* H = (struct ListNode*)malloc(sizeof(struct ListNode));  //创建一个H头,用来链接小于x
    struct ListNode* H1 = (struct ListNode*)malloc(sizeof(struct ListNode)); // 用来链接大于等于x
    struct ListNode* h = H;  
    struct ListNode* h1 = H1; 
    struct ListNode* p =head; 
    int k =0; int k1 = 0;  //用来保存H和H1长度，如果有一个为0，那么原链表要么全大于等于x,要么全小于x
    while(p!=NULL)
    { 
        if(p->val<x){ 
            h->next = p; h = h->next; k = 1; // 插入到H中
        } else { 
            h1->next = p; h1 = h1->next; k1 = 1;  //大于等于插入到H1
        } 
        p = p->next; 
    } 
    if(k&&k1){ 
        h->next = H1->next; h1->next = NULL; return H->next; //如果都k,k1不为0，就链接两个链表
    } else return head;  //否则返回原链表
  }
};

题解二：直接在原链表操作
题解思路： 将大于等于x放到链表的尾部，修改中间节点的next
图示：

复杂度分析：
时间复杂度：O(N)
空间复杂度：O(1)
实现如下：

class Solution {
public:
    /**
     *
     * @param head ListNode类
     * @param x int整型
     * @return ListNode类
     */
    ListNode* partition(ListNode* head, int x) {
        if(!head||!head->next) return head;
        ListNode* start = (struct ListNode*)malloc(sizeof(struct ListNode));  //创建一个空白节点，指向头，统一操作
        start->next = head;  //空白节点指向头
        ListNode* p = head;  
        while(p->next!=NULL) p = p->next; // p指向尾节点
        ListNode* q = start,*end = p;
        while(q->next!=end){  // q->next 不为尾节点
           if(q->next->val>=x){ // 大于等于x，将该节点next节点插入到尾部，修改节点next，修改p
               p->next = q->next;
               q->next = q->next->next;
               p->next->next = NULL;
               p = p->next;
           }
           else q = q->next;
       }
       if(end->val>=x){p->next = end;q->next = end->next; end->next = NULL;}  //特判原链表的尾部节点
       return start->next; 
    }
};