Given a singly linked list L: L0→L1→…→Ln-1→Ln,

reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes' values.

For example,

Given {1,2,3,4}, reorder it to {1,4,2,3}.

 

Subscribe to see which companies asked this question

解答：

第一种方法是利用快慢指针找到中间节点，然后反转后半部分链表后合并链表，当然这里要注意分类讨论奇数个节点和偶数个节点的情况，另外注意合并链表后新链表的结尾要赋值为NULL，否则主函数中遍历链表就是在遍历循环链表了……还有就是一如既往地要注意空表的情况……

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     struct ListNode *next; * }; */void reorderList(struct ListNode* head) {    struct ListNode *fast = head, *slow = head, *tmp, *tmp_head = NULL, *tmp_tail;        while(NULL != fast&&NULL != fast->next){        slow = slow->next;        fast = fast->next->next;    }    if(NULL == fast){        tmp_tail = slow;    }    else{        tmp_tail = slow->next;    }    while(NULL != tmp_tail){            tmp = tmp_tail->next;            tmp_tail->next = tmp_head;            tmp_head = tmp_tail;            tmp_tail = tmp;    }    slow = tmp_head;    if(NULL == fast){        while(NULL != slow){            tmp = slow->next;            slow->next = head->next;            if(NULL == tmp){                slow->next = NULL;            }            head->next = slow;            head = slow->next;            slow = tmp;        }    }    else{        while(NULL != slow){            tmp = slow->next;            slow->next = head->next;            head->next = slow;            head = slow->next;            slow = tmp;        }        head->next = NULL;    }}

第二种方法是利用堆栈FILO，这样的话顺序遍历链表将节点压入堆栈后，节点依次弹出链表的顺序就和题中要求的顺序吻合了，而且压入堆栈的过程中还得到了链表长度……这里需要注意的还有就是变量的值在操作中可能会更改，需要用临时变量来保存当前值…… 

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     struct ListNode *next; * }; */void reorderList(struct ListNode* head) {    struct ListNode* stack[100000];    struct ListNode *tmp = head;    int top = -1, size, tmp_val;        while(NULL != tmp){        stack[++top] = tmp;        tmp = tmp->next;    }    size = (top + 1) / 2;    tmp_val = top;    while(size){        size--;        tmp = stack[top];        top--;        tmp->next = head->next;        head->next = tmp;        head = tmp->next;    }    if(0 == tmp_val % 2){        head->next = NULL;    }    else if(NULL != tmp){        tmp->next = NULL;    }}