143. Reorder List

problem description

Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You may not modify the values in the list's nodes, only nodes itself may be changed.

Example 1:

Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2:

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

algorithm thought

这里我还是用的链表题通用解法，使用递归解决，但是这里用递归确实不是太好，时间复杂度会有O(n²),可以用一个vector先保存所有节点，再处理

code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
       head=reorder(head);
    }
    ListNode* reorder(ListNode* head){
        if(head==NULL||head->next==NULL||head->next->next==NULL)
          return head;
        ListNode* tmp=head;
        while(head->next->next){
            head=head->next;
        }

        head->next->next=tmp->next;
        tmp->next=head->next;
        head->next=NULL;
        tmp->next->next=reorder(tmp->next->next);
        return tmp;
    }
};

algorithm analysis

这里的算法算是很慢的了，时间复杂度达到了O(n²)，不是很建议使用，只是我比较喜欢用递归解链表题，所以这里才用递归解决