leetcode如何分隔链表

问题描述

给定一个链表和一个特定值x，要求将链表分隔成两部分，使得所有小于x的节点都位于大于或等于x的节点之前。

解决思路

问题可以通过创建两个新的链表来解决，分别是小于x的链表和大于或等于x的链表。然后遍历原链表，将小于x的节点插入到小于x的链表中，大于或等于x的节点插入到大于或等于x的链表中。最后将小于x的链表的尾节点指向大于或等于x的链表的头节点即可。

代码实现

public ListNode partition(ListNode head, int x) {
    ListNode smallerHead = new ListNode(0);  // 创建小于x的链表的头节点
    ListNode smaller = smallerHead;  // 创建临时指针指向小于x的链表
    ListNode greaterEqualHead = new ListNode(0);  // 创建大于或等于x的链表的头节点
    ListNode greaterEqual = greaterEqualHead;  // 创建临时指针指向大于或等于x的链表
    ListNode current = head;  // 创建遍历原链表用的指针

    while (current != null) {
        if (current.val < x) {  // 当前节点小于x时，插入到小于x的链表中
            smaller.next = current;
            smaller = smaller.next;
        } else {  // 当前节点大于或等于x时，插入到大于或等于x的链表中
            greaterEqual.next = current;
            greaterEqual = greaterEqual.next;
        }
        current = current.next;  // 移动指针到下一个节点
    }

    greaterEqual.next = null;  // 大于或等于x的链表的尾节点指向null
    smaller.next = greaterEqualHead.next;  // 将小于x的链表的尾节点指向大于或等于x的链表的头节点

    return smallerHead.next;  // 返回小于x的链表的头节点
}

算法分析

假设链表的长度为n。

1. 创建两个临时指针smaller和greaterEqual，所以时间复杂度为O(1)。

2. 遍历原链表，将节点插入到小于x的链表或大于或等于x的链表中，所以时间复杂度为O(n)。

3. 最后将小于x的链表的尾节点指向大于或等于x的链表的头节点，所以时间复杂度为O(1)。

综上所述，该算法的时间复杂度为O(n)。