C语言每日一题（30）分割链表

牛客网NC23 划分链表

题目描述

给出一个长度为 n 的单链表和一个值 x ，单链表的每一个值为 list，请返回一个链表的头结点，要求新链表中小于 x 的节点全部在大于等于 x 的节点左侧，并且两个部分之内的节点之间与原来的链表要保持相对顺序不变。

例如：

给出 1→4→3→2→5→2 和 x=3

返回 1→2→2→4→3→5

思路分析

将该链表小于x的部分和大于等于x的部分进行拆分分别用两个头结点指向，相当于分别存入两个链表里，最后将链表1（小于x的部分）的尾结点指向链表2（大于等于x的部分）的首结点即可。

完整代码

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param head ListNode类
 * @param x int整型
 * @return ListNode类
 */
struct ListNode* partition(struct ListNode* head, int x ) {
    struct ListNode* head1, *head2, *tail1, *tail2;
    head1 = tail1 = (struct ListNode*)malloc(sizeof(struct ListNode));//两个哨兵位
    head2 = tail2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* cur = head;
    if (head == NULL) {//链表为空的情况直接返回头结点即可
        return head;
    } else {
        while (cur) {
            if (cur->val < x) {//小于x的值放到链表1里
                tail1->next = cur;
                tail1 = tail1->next;
 
            } else {//大于等于x的值放到链表2里
                tail2->next = cur;
                tail2 = tail2->next;
            }
            cur = cur->next;//遍历原数组
        }
        tail1->next = head2->next;//链表1的末尾指向链表2的头
 
        tail2->next = NULL;//注意置空
 
        head = head1->next;
        free(head1);//记得释放哨兵位
        free(head2);
        return head;
    }
}

实现细节

采用两个哨兵位创建两个链表，避免头结点为空的情况（本人正在努力实现不带哨兵位的情况（doge））。