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}.

 

看上去有点难，实际上可以分为几个步骤。

1.找到中间节点。划分为两个链表。（算法总结里有）

2.把后半部分链表反转。（算法总结里有）

3.合并两个链表。（递归）

1 /** 2  * Definition for singly-linked list. 3  * struct ListNode { 4  *     int val; 5  *     ListNode *next; 6  *     ListNode(int x) : val(x), next(NULL) {} 7  * }; 8  */ 9 class Solution {10 public:11     ListNode* ReverseList(ListNode* head){12     if(head==NULL||head->next==NULL)13         return head;14     ListNode* p=head->next,*q=head,*l=head;15     while(p->next!=NULL){16         l=p->next;17         p->next=q;18         q=p;19         p=l;20     }21     p->next=q;22     head->next=NULL;23     return p;24 }25 ListNode* Merge(ListNode* l1,ListNode* l2){26     if(l1==NULL)27         return l2;28     if(l2==NULL){29         l1->next=NULL;30         return l1;31     }32     ListNode* p=l1,*q=l2;33     l1=l1->next;34     l2=l2->next;35     p->next=q;36     q->next=Merge(l1,l2);37     return p;38 }39     void reorderList(ListNode* head) {40         if(head==NULL||head->next==NULL)41             return;42         ListNode* p=head,*q=head,*bf=NULL;43         while(p&&p->next!=NULL){44             p=p->next->next;45             bf=q;46             q=q->next;47     }48     bf->next=NULL;49     q=ReverseList(q);50     Merge(head,q);51     return;52     }53 };