LeetCode 面试题02.04.分割链表

LeetCode 面试题02.04.分割链表 C写法

思路：

​ 将x分为两段，一段放小于x的值，另一段放大于x的值。开辟四个指针lesshead、lesstail、greaterhead、greatertail，head为哨兵位，防止链表为空时情况过于复杂，tail为尾结点，将链表的值进行大小判断后尾插完成分段，分段后再链接，最后释放哨兵位完成整个链表的分割。

代码：

struct ListNode* partition(struct ListNode* head, int x){
       struct ListNode* lesshead,*lesstail,*greaterhead,*greatertail;
       lesshead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode));
       greaterhead = greatertail = (struct ListNode*)malloc(sizeof(struct ListNode));
       lesstail->next = greatertail->next = NULL; //将链表分为两段存储
       struct ListNode* cur = head;
       while(cur)
       {
            if(cur->val < x) //小于x尾插在less段
            {
                lesstail->next = cur;
                lesstail = lesstail->next;
            }
            else
            {
                greatertail->next = cur;
                greatertail = greatertail->next;
            }
            cur = cur->next;
       }
       lesstail->next = greaterhead->next; //链接两段链表，哨兵位不放数据所以要链接到next
       greatertail->next = NULL; //单链表最后要指向空
       struct ListNode* list = lesshead->next; //完整链表
       free(greaterhead);
       free(lesshead);
       return list;
}