链表题目练习----重排链表

这道题会联系到前面写的一篇文章----快慢指针相关经典问题。

重排链表

指针法

这道题乍一看，好像有点难处理，但如果仔细观察就会发现，这道题是查找中间节点+反转链表+链表的合并问题，具体细节有些不同，这个在反装中间链表时，要从中间节点的下一个位置开始反装，具体过程如下。

代码实现：

typedef struct ListNode Node;

Node* ReverseList(struct ListNode* head)
{
    Node* cur = head;
    Node* n1 = NULL, *n2 = head, *n3 = head->next;
    while (n2)
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if (n3)
            n3 = n3->next;
    }
    return n1;
}

Node* MidList(struct ListNode* head)
{
    Node* fast = head, *slow = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        if(fast)
            fast = fast->next->next;
    }
    return slow;
}

void reorderList(struct ListNode* head)
{
    if (head == NULL || head->next == NULL || head->next->next == NULL)
    {
        return;
    }
    Node* cur = head, *mid = MidList(head);
    Node* rev = ReverseList(mid->next);
    mid->next = NULL;
    Node* tmp1 = cur, *tmp2 = rev;
    while (cur && rev)
    {
        tmp1 = cur->next;
        tmp2 = rev->next;
        cur->next = rev;
        cur = tmp1;
        rev->next = cur;
        rev = tmp2;
    }
}

数组法

数组法就是利用数组直接存储每个节点，然后直接插入排序。首先开辟一个类型为struct ListNode*的数组存储每个节点，然后就重排。

这个我们直接上代码

typedef struct ListNode Node;

void reorderList(struct ListNode* head)
{
    //如果是这种情况下，重排的结果与原链表相同，我们直接返回
    if (head == NULL || head->next == NULL || head->next->next == NULL)
    {
        return;
    }
    //开辟数组
    Node* arr[40001];
    Node* cur = head;
    int n = 0;
    //存储每个节点的值
    while(cur)
    {
        arr[n++] = cur;
        cur = cur->next;
    }
    //开始重排
    int i = 0, j = n - 1;
    while (i < j)
    {
        //直接在原链表中操作，不用担心覆盖问题，因为这些值在数组中均有存储
        arr[i]->next = arr[j];
        i++;

        if (i == j)
        {
            break;
        }

        arr[j]->next = arr[i];
        j--;
    }
    //最后不要忘了把重排后的最后一个位置置为空，防止成环
    //这里直接置最后i位置的值为空，我们等会画图解释
    arr[i]->next = NULL;
}