一、题目描述
给你一个链表的头节点 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
二、解题思路
- 创建两个新的链表，一个用于存储小于x的节点（我们称之为小于链表），另一个用于存储大于或等于x的节点（我们称之为大于等于链表）。
- 遍历原始链表，根据节点的值将节点添加到小于链表或大于等于链表中。
- 将小于链表的尾部连接到大于等于链表的头部，得到新的链表。
- 返回新链表的头节点。
三、具体代码
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode partition(ListNode head, int x) {ListNode dummy1 = new ListNode(0); // 创建小于链表的哑节点ListNode dummy2 = new ListNode(0); // 创建大于等于链表的哑节点ListNode less = dummy1; // 小于链表的当前节点ListNode greaterOrEqual = dummy2; // 大于等于链表的当前节点while (head != null) {if (head.val < x) {less.next = head; // 将节点添加到小于链表中less = less.next; // 移动小于链表的当前节点} else {greaterOrEqual.next = head; // 将节点添加到大于等于链表中greaterOrEqual = greaterOrEqual.next; // 移动大于等于链表的当前节点}head = head.next; // 移动原始链表的当前节点}greaterOrEqual.next = null; // 设置大于等于链表的尾部为nullless.next = dummy2.next; // 将小于链表的尾部连接到大于等于链表的头部return dummy1.next; // 返回新链表的头节点}
}
四、时间复杂度和空间复杂度
1. 时间复杂度
- 遍历原始链表一次，对于每个节点，我们执行常数时间的操作（比较节点的值，然后将其添加到对应的链表中）。
- 因此，时间复杂度是 O(n)，其中 n 是链表中的节点数。
2. 空间复杂度
- 我们创建了两个哑节点，分别用于小于链表和大于等于链表，这两个节点不存储有效的链表数据，所以它们不计入空间复杂度。
- 我们没有创建任何新的节点，只是重新排列了现有的节点。
- 因此，空间复杂度是 O(1)，即常数空间复杂度。
综上所述，这段代码的时间复杂度是 O(n)，空间复杂度是 O(1)。
五、总结知识点
1. 链表操作：
- 链表是线性数据结构，由节点组成，每个节点包含数据和指向下一个节点的引用。
- 代码中创建了两个哑节点，分别用于小于x的节点和大于等于x的节点，这样可以避免处理空链表的特殊情况。
2. 哑节点的使用：
- 哑节点是一种常用的技巧，用于简化链表操作，特别是在处理链表的头节点时。
- 它作为一个不存储有效数据的节点，其next指针指向链表的真正头部，这样可以避免对头节点的特殊处理。
3. 链表的遍历：
- 使用while循环和当前节点的移动（
head = head.next;）来遍历链表。 - 在遍历过程中，根据节点的值将节点添加到小于链表或大于等于链表中。
4. 链表的分割：
- 通过调整节点的next指针，将原始链表分割成两个部分，一个包含小于x的节点，另一个包含大于等于x的节点。
- 最后，将小于链表的尾部连接到大于等于链表的头部，形成一个新的链表。
5. 指针和引用：
- 在链表操作中，使用指针（在Java中是引用）来跟踪当前节点和链表的头部。
- 通过更新这些指针，可以重新排列链表中的节点。
6. 链表与递归：
- 虽然这段代码没有使用递归，但链表问题通常也可以通过递归方法解决。
- 递归可以简化链表的操作，尤其是在处理反向链表或复杂的链表操作时。
7. 边界条件的处理：
- 在链表操作中，需要特别注意边界条件，如空链表、单个节点的链表等。
- 代码中通过检查
head != null来确保在链表为空时不会发生错误。
以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。
