Medium

题目描述

给定单链表的头节点 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]

提示：

  • 链表中节点数在范围 [0, 10⁴] 内
  • -10⁶ <= Node.val <= 10⁶

解题思路

这道题要求我们将链表按照节点位置的奇偶性重新排列。核心思路是分离奇偶位置的节点，然后重新连接。

解法分析：

最优解法是使用双指针技术，分别维护奇数位置和偶数位置的链表：

  1. 初始化指针：使用 odd 指针指向第一个节点（奇数位置），even 指针指向第二个节点（偶数位置），同时保存 evenHead 作为偶数链表的头节点。

  2. 分离过程：通过交替连接的方式，将奇数位置的节点连接成一条链，偶数位置的节点连接成另一条链。具体操作是：

    • odd.next = even.next（跳过偶数节点，连接下一个奇数节点）
    • even.next = odd.next（跳过奇数节点，连接下一个偶数节点）

  3. 合并链表：最后将奇数链表的尾部连接到偶数链表的头部。

  4. 边界处理：需要考虑空链表、单节点链表等特殊情况。

这种方法的优势在于只需要 O(1) 的额外空间，通过原地修改指针实现重排，时间复杂度为 O(n)，满足题目要求。

代码实现

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (!head || !head->next) return head;
        
        ListNode* odd = head;
        ListNode* even = head->next;
        ListNode* evenHead = even;
        
        while (even && even->next) {
            odd->next = even->next;
            odd = odd->next;
            even->next = odd->next;
            even = even->next;
        }
        
        odd->next = evenHead;
        return head;
    }
};

class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        
        odd = head
        even = head.next
        even_head = even
        
        while even and even.next:
            odd.next = even.next
            odd = odd.next
            even.next = odd.next
            even = even.next
        
        odd.next = even_head
        return head

public class Solution {
    public ListNode OddEvenList(ListNode head) {
        if (head == null || head.next == null) return head;
        
        ListNode odd = head;
        ListNode even = head.next;
        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;
    }
}

var oddEvenList = function(head) {
    if (!head || !head.next) return head;
    
    let odd = head;
    let even = head.next;
    let evenHead = even;
    
    while (even && even.next) {
        odd.next = even.next;
        odd = odd.next;
        even.next = odd.next;
        even = even.next;
    }
    
    odd.next = evenHead;
    return head;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历链表中的每个节点一次
空间复杂度O(1)只使用了常数个额外指针变量

相关题目