济南市做网站,企业所得税税收筹划,梵克雅宝手链,中国手机网站大全给你一个链表的头节点 head 和一个特定值 x #xff0c;请你对链表进行分隔#xff0c;使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。 示例 1#xff1a; 输入#xff1a;head [1,4,3,2,5,2], x 3
输出请你对链表进行分隔使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。 示例 1 输入head [1,4,3,2,5,2], x 3
输出[1,2,2,4,3,5]
思路一创建新链表进行修改
struct ListNode* partition(struct ListNode* head, int x){struct ListNode*p1Head(struct ListNode *)malloc(sizeof(struct ListNode));struct ListNode*p2Head(struct ListNode *)malloc(sizeof(struct ListNode));struct ListNode*p1p1Head;struct ListNode*p2p2Head;struct ListNode*phead;while(p){if(p-valx){p1-nextp;p1p;}else{p2-nextp;p2p;}pp-next;}p2-nextNULL;p1-nextp2Head-next;return p1Head-next;}分析
本题将小于x的节点全部放在前面可新建两个个链表一个存储小于x的节点一个储存大于等于x的节点然后连接两个链表再返回新链表
思路二原地修改 struct ListNode* partition(struct ListNode* head, int x){struct ListNode dummy;dummy.next head;struct ListNode* slow dummy;while(slow-next ! NULL slow-next-valx){slow slow-next;}struct ListNode* fast slow;while(fast fast-next){if(fast-next-val x){struct ListNode* tmp fast-next;fast-next tmp-next;tmp-next slow-next;slow-next tmp;slow slow-next;}elsefast fast-next;}return dummy.next;
}
分析
本题还可使用双指针原地修改链表将小于x 的节点移动到链表前部。创建一个虚拟头节点 dummy并将其指向原链表的头部遍历链表找到第一个大于等于 x 的节点将慢指针 slow 移动到该节点的前一个位置通过快指针向后遍历将小于x的节点放置在慢指针后最后输出
总结
本题有两种解题思路创建新链表来存放小于x和大于x的数或利用双指针直接修改原链表考察了链表相关操作利用好指针或新建链表即可解决
