[143] Reorder List

要重新排列linked list
例如 : 1,2,3,4,5,6
要排成 : 1,6,2,5,3,4
真囉唆XD
照著直觀的解釋下去解,得到了18xx ms 的傲人成績！！！
（根本就是超過time limit 的邊緣 XD～）
於是就想到了可以切一半的作法;
沒想到還是不夠 囧
看別人講的, 還要再給它reverse 一下最後組回去才是相對快的解法
唉我還是奔入雨中吧.............

超出時間版
Reorder List

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     struct ListNode *next;

 * };

 */

void reorderList(struct ListNode* head) {

    if (head == NULL)

        return;

    if (head->next == NULL)

        return;

    if (head->next->next == NULL)

        return;

    struct ListNode *end, *ptr, *pcur, *ppre;

    pcur = head;

    

    while(pcur->next != NULL && pcur->next ->next != NULL)

    {

        for(ppre = head, ptr = head -> next; ptr->next != NULL;ppre=ppre->next, ptr = ptr->next)

            ;

        ppre->next = NULL;

        end = ptr;

        end->next = pcur->next;

        pcur->next = end;

        pcur = end->next;

    }

}

不過呢, 以往linked list都要寫很久的我,

這題倒是沒卡關很久

雖然超時了哈哈但是還是蠻欣慰的QQ

(廢啊這孩子XD)

所以就直接給它切一半, 但是反骨不想做reverse:

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     struct ListNode *next;

 * };

 */

void reorderList(struct ListNode* head) {

    if (head == NULL)

        return;

    if (head->next == NULL)

        return;

    if (head->next->next == NULL)

        return;

    struct ListNode *end, *ptr, *pcur, *ppre,*middle;

    pcur = head;

    int i,count=0;

    for(ptr = head;ptr->next != NULL;ptr= ptr->next)

    {

        count++;

    }

    for(ptr = head,i=0;i<(count/2);ptr= ptr->next, i++)

    ;

    middle = ptr;

    

    while(pcur->next != NULL && pcur->next ->next != NULL)

    {

        for(ppre = middle, ptr = middle -> next; ptr->next != NULL;ppre=ppre->next, ptr = ptr->next)

            ;

        ppre->next = NULL;

        end = ptr;

        end->next = pcur->next;

        pcur->next = end;

        pcur = end->next;

    }

}

這樣時間已經快了四倍有 囧

有閒情逸致再來做反轉版Orz

20240525 update

說好的reverse版本XD

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* struct ListNode *next;

* };

*/

struct ListNode* reverse(struct ListNode* head)

{

struct ListNode *pre, *cur,*next;

pre = NULL;

cur = head;

while(cur != NULL)

{

next = cur->next;

cur->next = pre;

pre = cur;

cur = next;

}

return pre;

}

void reorderList(struct ListNode* head) {

if (head == NULL || head->next == NULL)

return;

struct ListNode *fast, *slow, *pre;

fast= head;

slow= head;

pre = NULL;

while (fast != NULL )

{

fast = fast->next;

if (fast != NULL)

fast = fast->next;

pre= slow;

slow = slow->next;

}

pre->next= NULL;

fast = reverse(slow);//later half head

slow = head; // just a pointer

while (slow != NULL)

{

struct ListNode* p1 = slow->next;

slow->next = fast;

if (fast->next == NULL)

{

fast->next = p1;

break;

}

struct ListNode* p2 = fast->next;

fast->next = p1;

fast= p2;

slow =p1;

}

}