网站建设方案预算费用预算,聚美优品网站建设导向,网站程序员,广告电商怎么赚钱目录
一、分割链表
二、奇偶链表 一、分割链表
给你一个链表的头节点 head 和一个特定值 x #xff0c;请你对链表进行分隔#xff0c;使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你不需要 保留 每个分区中各节点的初始相对位置。
示例 1#xff1a; 输…目录
一、分割链表
二、奇偶链表 一、分割链表
给你一个链表的头节点 head 和一个特定值 x 请你对链表进行分隔使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你不需要 保留 每个分区中各节点的初始相对位置。
示例 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
代码实现
struct ListNode* partition(struct ListNode* head, int x)
{struct ListNode* lessGuard (struct ListNode*)malloc(sizeof(struct ListNode));lessGuard-next NULL;struct ListNode* lessTail lessGuard;
struct ListNode* greaterGuard (struct ListNode*)malloc(sizeof(struct ListNode));greaterGuard-next NULL;struct ListNode* greaterTail greaterGuard;// 将小于 x 的结点尾插到第一个链表中// 将大于或等于 x 的结点尾插到第二个链表中struct ListNode* cur head;while (cur ! NULL){if (cur-val x){lessTail-next cur;lessTail cur;}else{greaterTail-next cur;greaterTail cur;}cur cur-next;}// 链接这两个链表lessTail-next greaterGuard-next; // (1)greaterTail-next NULL; // (2)// 返回head lessGuard-next;free(lessGuard);free(greaterGuard);return head;
}
图解示例一 二、奇偶链表
给定单链表的头节点 head 将所有索引为奇数的节点和索引为偶数的节点分别组合在一起然后返回重新排序的列表。
第一个节点的索引被认为是 奇数 第二个节点的索引为 偶数 以此类推。
请注意偶数组和奇数组内部的相对顺序应该与输入时保持一致。
你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。
示例 1 输入: head [1,2,3,4,5] 输出: [1,3,5,2,4] 示例 2 输入: head [2,1,3,5,6,4,7] 输出: [2,3,6,7,1,5,4] 提示 n 链表中的节点数 0 n 104 -106 Node.val 10^6
代码实现
struct ListNode* oddEvenList(struct ListNode* head)
{if (head NULL){return head;}struct ListNode* odd head;struct ListNode* even head-next;struct ListNode* evenHead even;while (even ! NULL even-next ! NULL){odd-next even-next; odd odd-next;even-next odd-next;even even-next;}odd-next evenHead;return head;
}
图解示例一
