题解 | #链表的奇偶重排#

这道题还是非常简单的~因为复杂度限制非常宽松，所以可以使用非常笨的方法去实现啦~

简而言之，题目希望我们将链表中修改成奇节点+偶节点的格式。我们采取的方法还是像之前那样首先遍历链表获取链表长度，然后根据奇偶关系得到奇数数组的长度应该是len/2+1(len为奇数)或者len/2(len为偶数)，偶数数组的长度应该为len/2。

然后我们根据index的奇偶将链表中的值存入数组中，然后新建一个链表就好了~

我这里误解了题目的意思，写了一个归并排序哈哈哈

int getlen(struct ListNode* head)
{
    int len = 0;
    while(head!=NULL)
    {
        len++;
        head = head->next;
    }
    return len;
}
struct ListNode* createnode(int val)
{
    struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
    if(node!=NULL)
    {
        node->val = val;
        node->next = NULL;
    }
    return node;
}
void merge(int arr[],int left,int mid,int right)
{
    int len1 = mid-left+1;
    int len2 = right - mid;
    int arr1[len1];
    for(int i=0;i<len1;i++)
    {
        arr1[i] = arr[left+i];
    }
    int arr2[len2];
    for(int i=0;i<len2;i++)
    {
        arr2[i] = arr[mid+1+i];
    }
    int out[right-left+1];
    int pos = 0;
    int pos_1 = 0;
    int pos_2 = 0;
    while(pos_1<len1&&pos_2<len2)
    {
        if(arr1[pos_1]<arr2[pos_2])
        {
            out[pos] = arr1[pos_1];
            pos_1++;
        }
        else if(arr1[pos_1]>=arr2[pos_2])
        {
            out[pos] = arr2[pos_2];
            pos_2++;
        }
        pos++;
    }
    while(pos_1<len1)
    {
        out[pos] = arr1[pos_1];
        pos_1++;    
        pos++;
    }
    while(pos_2<len2)
    {
        out[pos] = arr2[pos_2];
        pos_2++;    
        pos++;
    }
    for(int i=0;i<right-left+1;i++)
    {
        arr[left+i] = out[i];
    }
}
void mergesort(int arr[],int left,int right)
{
    if(left>=right)
    {
        return ;
    }
    int mid = (right+left)/2;
    mergesort(arr, left, mid);
    mergesort(arr, mid+1,right);
    merge(arr,left,mid,right);
}
struct ListNode* oddEvenList(struct ListNode* head ) {
    // write code here
    if(head==NULL)
    {
        return NULL;
    }
    struct ListNode* para_head = head;
    int len = getlen(para_head);
    int odd_len, even_len;
    if(len%2==0)
    {
        odd_len = len/2;
        even_len = len/2;
    }
    else   
    {
        odd_len = len/2+1;
        even_len = len/2;
    }
    int odd_arr[odd_len];
    int even_arr[even_len];
    int pos = 1;
    int pos_even = 0;
    int pos_odd =  0;
    while(head!=NULL)
    {
        if(pos%2==0)
        {
            even_arr[pos_even] = head->val;
            pos_even++;
        }
        else   
        {
            odd_arr[pos_odd] = head->val;
            pos_odd++;
        }
        pos++;
        head = head->next;
    }
    for(int i=0;i<odd_len;i++)
    {
        printf("%d ",odd_arr[i]);
    }printf("\n");
    // mergesort(odd_arr, 0, odd_len-1);
    // mergesort(even_arr,0, even_len-1);
    struct ListNode* newhead = createnode(odd_arr[0]);
    struct ListNode* out = newhead;
    for(int i=1;i<odd_len;i++)
    {
        struct ListNode* node = createnode(odd_arr[i]);
        newhead->next = node;
        newhead = newhead->next;
    }
    for(int i=0;i<even_len;i++)
    {
        struct ListNode* node = createnode(even_arr[i]);
        newhead->next = node;
        newhead = newhead->next;
    }
    return out;
}