⭐ 题目日期：

字节 - 2024/11/24, 字节 - 2024/10/17

🌳 题目描述：

一个链表，单索引是递增的，双索引是递减的，请对它进行升序排序，要求O(1)空间复杂度

示例 1:

🕵🏽 面试评估：

这道题主要考查对复杂模型的拆解能力、链表的常见操作以及实现不同功能的代码编写能力，综合难度中等偏上。

🧗难度系数：

⭐️ ⭐️ ⭐️ ⭐️

📝思路分析：

两个递增的链表升序排列或者两个递减的链表降序排列比较容易。那我们能不能转化为同增同减呢？既然单索引是递增的，双索引是递减，那我们按单双索引分解成两个链表：

递增：1 → 3 → 5

递减：6 → 4 → 2

再将递减的反转得到：

2 → 4 → 6

这样我们就将问题转化为对两条递增的链表进行排序。

1 → 3 → 5

2 → 4 → 6

建一个dummyNode, 1 < 2, 排序得到 dummyNode -> 1, 剩下的链表为：

3 → 5

2 → 4 → 6

2 < 3, 排序得到 dummyNode -> 1 -> 2, 剩下的链表为：

3 → 5

4 → 6

重复以上过程，得到dummyNode -> 1 -> 2 -> 3 -> 4 -> 5 -> 6，返回dummyNode.next

💻代码：

Java

public ListNode sortLinkedList(ListNode head) {
    if (head == null || head.next == null)
        return head;

    // 分离链表为单索引和双索引两个子链表, 并返回链表的头节点，0 - oddHead, 1 - evenHead
    List<ListNode> heads = splitLists(head);

    // 反转双索引子链表（递减顺序）变为递增顺序
    ListNode reversedEven = reverseList(heads.get(1));

    // 合并两个递增子链表
    ListNode mergedHead = mergeTwoSortedLists(heads.get(0), reversedEven);

    return mergedHead;
}

private List<ListNode> splitLists(ListNode head) {
    List<ListNode> heads = new ArrayList<>();
    ListNode oddHead = new ListNode(0);  // 哑节点，用于构建单索引子链表
    ListNode evenHead = new ListNode(0); // 哑节点，用于构建双索引子链表
    ListNode odd = oddHead;
    ListNode even = evenHead;
    ListNode cur = head;
    boolean isOdd = true;

    while (cur != null) {
        if (isOdd) {
            odd.next = cur;
            odd = odd.next;
        } else {
            even.next = cur;
            even = even.next;
        }
        cur = cur.next;
        isOdd = !isOdd;
    }

    // 断开原链表的连接
    odd.next = null;
    even.next = null;

    heads.add(oddHead.next);
    heads.add(evenHead.next);
    return heads;
}

private ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode cur = head;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }

    return prev;
}

private ListNode mergeTwoSortedLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode cur = dummy;

    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            cur.next = l1;
            l1 = l1.next;
        } else {
            cur.next = l2;
            l2 = l2.next;
        }
        cur = cur.next;
    }

    // 连接剩余部分
    if (l1 != null) {
        cur.next = l1;
    } else {
        cur.next = l2;
    }

    return dummy.next;
}

Python

def sortLinkedList(head):
    if not head or not head.next:
        return head

    # 分离链表为单索引和双索引两个子链表
    heads = splitLists(head)

    # 反转双索引子链表
    reversedEven = reverseList(heads[1])

    # 合并两个递增子链表
    mergedHead = mergeTwoSortedLists(heads[0], reversedEven)

    return mergedHead

def splitLists(head):
    heads = []
    odd_Head = ListNode(0)  # 哑节点，用于构建单索引子链表
    even_Head = ListNode(0)  # 哑节点，用于构建双索引子链表
    odd = odd_Head
    even = even_Head
    cur = head
    is_Odd = True

    while cur:
        if is_Odd:
            odd.next = cur
            odd = odd.next
        else:
            even.next = cur
            even = even.next
        cur = cur.next
        is_Odd = not is_Odd

    # 断开原链表的连接
    odd.next = None
    even.next = None

    heads.append(odd_Head.next)
    heads.append(even_Head.next)
    return heads

def reverseList(head):
    prev = None
    cur = head
    while cur:
        next_node = cur.next
        cur.next = prev
        prev = cur
        cur = next_node
    return prev

def mergeTwoSortedLists(l1, l2):
    dummy = ListNode(0)
    cur = dummy

    while l1 and l2:
        if l1.val <= l2.val:
            cur.next = l1
            l1 = l1.next
        else:
            cur.next = l2
            l2 = l2.next
        cur = cur.next

    # 连接剩余部分
    if l1:
        cur.next = l1
    else:
        cur.next = l2

    return dummy.next

🚵🏻复杂度分析：

时间复杂度: O(n), O(n) 分离单双索引链表，O(n / 2) 反转双索引递减链表，O(n) 合并两个递增子链表，所以总的时间复杂度为 O(n)。

空间复杂度: O(1)，仅用常数级空间存储变量。