分隔链表
- 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
示例 1：
输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
解题思路
- 将链表分隔成两部分，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前，同时保留原有节点的相对位置。
- 使用两个指针分别构建两个链表：
-
1、小于 x 的节点构成一个链表。 -
2、大于或等于 x 的节点构成另一个链表。 -
3、最后将这两个链表连接起来。
Java实现
public class PartitionLinked {public static class ListNode {int val;ListNode next;ListNode(int x) { val = x; }}public ListNode partition(ListNode head, int x) {// 创建两个哨兵节点ListNode before = new ListNode(0);ListNode after = new ListNode(0);// 指向当前处理节点的指针ListNode beforeHead = before;ListNode afterHead = after;// 遍历原链表ListNode current = head;while (current != null) {if (current.val < x) {//加入before链表before.next = current;before = before.next;} else {//加入after链表after.next = current;after = after.next;}current = current.next;}// 连接两个链表after.next = null;before.next = afterHead.next;return beforeHead.next;}public static void main(String[] args) {PartitionLinked partitionLinked = new PartitionLinked();// 创建示例链表 1->4->3->2->5->2ListNode head = new ListNode(1);head.next = new ListNode(4);head.next.next = new ListNode(3);head.next.next.next = new ListNode(2);head.next.next.next.next = new ListNode(5);head.next.next.next.next.next = new ListNode(2);// 分隔链表ListNode newHead = partitionLinked.partition(head, 3);printList(newHead); // 输出: 1->2->2->4->3->5}// 辅助方法：打印链表public static void printList(ListNode head) {ListNode current = head;while (current != null) {System.out.print(current.val);if (current.next != null) {System.out.print("->");}current = current.next;}System.out.println();}
}
时间空间复杂度
- 时间复杂度：O(n)，其中 n 是链表的节点数。需要遍历链表一次。
- 空间复杂度：O(1)。
