问题描述 :
给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1:
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
示例 2:
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
输入说明 :
首先输入链表长度len，然后输入len个整数，以空格分隔。
输出说明 :
输出格式见范例
#include<iostream> using namespace std; struct ListNode{ int val; struct ListNode *next; ListNode() : val(0), next(NULL) {} ListNode(int x) : val(x), next(NULL) {} ListNode(int x, ListNode *next) : val(x), next(next) {} }; class Solution { public: void reorderList(ListNode* head) { //编写该功能的代码 ListNode *p,*q,*q_pre,*r; p=head;r=head;q=head; if(!head)return; while(p->next) { r=p->next; while(q->next->next){ q=q->next; } if(r->next){ q_pre=q; q=q->next; q->next=p->next; p->next=q; q_pre->next=NULL; p=r; r=p->next; } else break; } } }; ListNode *createByTail() { ListNode *head; ListNode *p1,*p2; int n=0,num; int len; cin>>len; head=NULL; while(n<len && cin>>num) { p1=new ListNode(num); n=n+1; if(n==1) head=p1; else p2->next=p1; p2=p1; } return head; } void displayLink(ListNode *head) { ListNode *p; p=head; cout<<"head-->"; while(p!= NULL) { cout<<p->val<<"-->"; p=p->next; } cout<<"tail\n"; } int main() { ListNode* head = createByTail(); Solution().reorderList(head); displayLink(head); return 0; }注意：当num为双数时的交换终止条件为 if(r->next)
