牛客网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的部分）的首结点即可。
完整代码
代码语言：javascript复制/**
* 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））。
