1、题目介绍
示例 1:
输入:head = [1,4,3,2,5,2], x = 3
输出:[1,2,2,4,3,5]
示例 2:
输入:head = [2,1], x = 2
输出:[1,2]
提示:
- 链表中节点的数目在范围 [0, 200] 内
- -100 <= Node.val <= 100
- -200 <= x <= 200
2、解题思路
根据题意,考虑通过「新建两个链表」实现原链表分割,算法流程为:
- 新建两个链表 small 和 BigEqu ,分别用于链接小于标志数 x 的结点和大于等于标志数 x 的结点。
- 遍历链表head并依次比较各节点值 head->val 和 x 的大小,若head->val < x ,则将head指向的该结点添加到链表 small 最后面。若head->val >= x,则将head指向的该结点添加到链表BigEqu最后面。
- 遍历完成后,拼接 small 和 BigEqu 链表。
- 最终判断头结点并返回。
2.1、双链表双指针
首先比较head->val与x,发现此时head->val小于x,因此放入small链表中,此时small的链头smallH和链尾smallT都指向结点1。head指向下一个结点。
继续比较head->val与x,发现此时head->val大于x,因此放入BigEqu链表中,此时BigEqu的链头BigEquH和链尾BigEquT都指向结点4。head指向下一个结点。
继续比较head->val与x,发现此时head->val等于x,因此放入BigEqu链表中,此时BigEqu的链尾BigEquT指向结点3。head指向下一个结点。
继续比较head->val与x,发现此时head->va小于x,因此放入small链表中,此时small的链尾smallT指向结点2。head指向下一个结点。
继续比较head->val与x,发现此时head->va大于x,因此放入BigEqu链表中,此时BigEqu的链尾BigEquT指向结点5。head指向下一个结点。
继续比较head->val与x,发现此时head->va小于x,因此放入small链表中,此时small的链尾smallT指向结点2。head指向下一个结点,此时head为null,则停止循环。
此时以smallH为链头的链表就是小于标志数 x 的结点集,以BigEqu为链头的链表就是大于等于标志数 x 的结点集,只需要将small链表的链尾smallT的next指向BigEqu链表的链头,最后返回small的 链头smallT 即可。
2.2、代码描述
循环的过程都比较好理解,就是最后合并链表时需要考虑特殊情况,如果没有小于标志数的结点时,此时返回的链头就不是smallH了,而是BigEqu的链头BigEquH。
struct ListNode* partition(struct ListNode* head, int x){ struct ListNode* smallH = NULL; //小于头 struct ListNode* smallT = NULL; //小于尾 struct ListNode* BigEquH = NULL; //大于等于头 struct ListNode* BigEquT = NULL; //大于等于尾 struct ListNode* next = NULL; //小于连一起,大于等于连一起 while(head) { next = head->next; //用next保存head的next,然后将head->置为空 head->next = NULL; //确保此时的head的next置为空,不然可能会导致死循环报错 if(head->val < x) //小于标志数 { if(smallH == NULL) //等于NULL表示第一次放入结点, //此时链头链尾都指向同一个结点 { smallH = smallT = head; } else //small的链尾的next指向head { smallT->next = head; smallT = head; } } else //大于等于标志数 { if(BigEquH == NULL) //同理 { BigEquH = BigEquT = head; } else { BigEquT->next = head; BigEquT = head; } } head = next; //head指向下一个结点 } //判断是否可以尾接头 if(smallT != NULL) //当small链尾不为空,即small链表有结点时, //才让small链尾连接BigEqu链头 { smallT->next = BigEquH; } return smallH == NULL ? BigEquH : smallH; //当small链表没有结点时,返回链头BigEquH, //否则返回链头smallH }
更多【LeetCode刷题】 推荐:
【LeetCode力扣】LCR170 使用归并排序的思想解决逆序对问题(详细图解
【LeetCode力扣】75 快速排序的子过程partition(荷兰国旗问题)
如果觉得作者写的不错,求给博主一个大大的点赞支持一下,你们的支持是我更新的最大动力!
如果觉得作者写的不错,求给博主一个大大的点赞支持一下,你们的支持是我更新的最大动力!
如果觉得作者写的不错,求给博主一个大大的点赞支持一下,你们的支持是我更新的最大动力!