【力扣】143. 重排链表

143. 重排链表

题目描述

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：

• 输入：head = [1,2,3,4]
• 输出：[1,4,2,3]

示例 2：

• 输入：head = [1,2,3,4,5]
• 输出：[1,5,2,4,3]

提示：

• 链表的长度范围为 [1, 5 * 104]
• 1 <= node.val <= 1000

解题方法

链表数组重排序

• C 语言

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
void reorderList(struct ListNode* head) {
    int len = 0;
    struct ListNode* str = head;
    // 定义链表数组
    struct ListNode* tab_list[50000];

    if (NULL == head) {
        return;
    }
    // 将链表存在数组中
    while (NULL != str) {
        tab_list[len++] = str;
        str = str->next;
    }
    // 定义双指针
    int left = 0, right = len - 1;
    // 重新排序链表
    while (left < right) {

        tab_list[left]->next = tab_list[right];
        left++;
        if (left == right) {
            break;
        }
        tab_list[right]->next = tab_list[left];
        right--;
    }
    tab_list[left]->next = NULL;
}

复杂度分析
时间复杂度为 O(N)，其中 N 是链表中的节点数。
空间复杂度为 O(N)，其中 N 是链表中的节点数。