两道有关链表的练习

目录

一、分割链表

二、奇偶链表

---

---

一、分割链表

给你一个链表的头节点 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;
}

图解示例一：