LeetCode Reorder List 新鲜出炉问题的解答

Reorder List

Given a singly linked list L: L_{0→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}.

终于调试出来了，考的是链表的操作，要对链表的操作非常清楚，否则也是很难调试的，总会有问题出来。我完成的时候50个accepted左右，提交的有400多。差不多10%多一点的通过率，看来还是有一定难度的了。

我的思路是：

1 计算链表长度

2 计算需要插入前面的元素，然后转置这些元素

3 用中间一个共有的元素作为结束点，循环插入。

不是很优化的算法，不过也accepted了。暂时没有想到更加优化的算法。

下面是程序。

class Solution {public:void reorderList(ListNode *(&head)) {if(head == nullptr || head->next == nullptr || head->next->next == nullptr) return;int n = listCount(head);int r = (n-1)/2;int i = 0;ListNode *pre = head;ListNode *cur = head;while (cur->next){cur=cur->next;if(i<r) i++;else pre=pre->next;}ListNode *tail;tail = reverseList(pre);ListNode *ph = head;while (ph != pre){insertBack(ph, tail);}ph->next = nullptr;}void insertBack(ListNode *(&head), ListNode *(&back)){ListNode *temp = back->next;back->next=head->next;head->next=back;head=back->next;back = temp;}ListNode* reverseList(ListNode *(&head)){if(head == nullptr || head->next == nullptr) return nullptr;ListNode *pre = head->next;ListNode *cur = head->next->next;ListNode *post;pre->next = head;if(cur == nullptr)return pre;if(cur->next != nullptr)post = cur->next;else{cur->next = pre;return cur;} cur->next = pre;while(post != nullptr){pre = cur;cur = post;post = post->next;cur->next = pre;}return cur;}int listCount(ListNode *head){int n = 0;ListNode *ph = head;while (ph!=nullptr){ph = ph->next;n++;}return n;}};