微软2014校招笔试编程题

Given asingly linked list L:(L0,L1,L2,...,Ln-1,Ln).Write a program to reorder it so that it becomes(L0,Ln,L1,Ln-1,L2,Ln-2,...)
struct Node
{
int val_;
Node* next;
};

Notes:

1.Space Complexity should be O(1)
2.Only the ".next" field of a node is modifiable.

新方法：[传送门]（2013.11.16 update）

  1 #include"stdafx.h"
  2 #include<iostream>
  3 using namespace std;
  4 
  5 struct Node
  6 {
  7     int val_;
  8     Node* next;
  9 };
 10 
 11 Node *CreateListNode(int key)
 12 {
 13     Node *ListNode=new Node;
 14     ListNode->val_=key;
 15     ListNode->next=NULL;
 16     return ListNode;
 17 }
 18 
 19 void ConnectListNodes(Node *ListNode1,Node *ListNode2)
 20 {
 21     ListNode1->next=ListNode2;
 22 }
 23 
 24 void PrintList(Node *ListHead)
 25 {
 26     Node* p=ListHead;
 27     while(p!=NULL)
 28     {
 29         cout<<p->val_<<" ";
 30         p=p->next;
 31     }
 32     cout<<endl;
 33 }
 34 
 35 void ReorderList(Node *ListHead)
 36 {
 37     Node *i,*j,*p,*q;
 38 
 39     i=ListHead;
 40     while(i&&i->next!=NULL)
 41     {
 42         j=i->next;
 43         p=i;
 44         q=i->next;
 45         while(q->next!=NULL)
 46         {
 47             p=p->next;
 48             q=q->next;
 49         }
 50         if(q!=j)
 51         {
 52             i->next=q;
 53             q->next=j;
 54             p->next=NULL;
 55         }
 56         else
 57         {
 58             i->next=q;
 59         }        
 60         i=j;
 61         j=j->next;
 62     }    
 63 }
 64 
 65 void DestroyList(Node *ListHead)
 66 {
 67     ListHead=NULL;
 68 }
 69 
 70 void Test(Node* ListHead)
 71 {
 72     PrintList(ListHead);
 73     ReorderList(ListHead);
 74     PrintList(ListHead);
 75 }
 76 // 0->1->2->3->4->5
 77 void Test1()
 78 {
 79     cout<<"Test1 begins."<<endl;
 80     Node *ListNode0=CreateListNode(0);
 81     Node *ListNode1=CreateListNode(1);
 82     Node *ListNode2=CreateListNode(2);
 83     Node *ListNode3=CreateListNode(3);
 84     Node *ListNode4=CreateListNode(4);
 85     Node *ListNode5=CreateListNode(5);
 86     ConnectListNodes(ListNode0,ListNode1);
 87     ConnectListNodes(ListNode1,ListNode2);
 88     ConnectListNodes(ListNode2,ListNode3);
 89     ConnectListNodes(ListNode3,ListNode4);
 90     ConnectListNodes(ListNode4,ListNode5);
 91 
 92     Test(ListNode0);
 93     DestroyList(ListNode0);
 94 }
 95 // 0->1->2->3->4->5->6
 96 void Test2()
 97 {
 98     cout<<"Test2 begins."<<endl;
 99     Node *ListNode0=CreateListNode(0);
100     Node *ListNode1=CreateListNode(1);
101     Node *ListNode2=CreateListNode(2);
102     Node *ListNode3=CreateListNode(3);
103     Node *ListNode4=CreateListNode(4);
104     Node *ListNode5=CreateListNode(5);
105     Node *ListNode6=CreateListNode(6);
106     ConnectListNodes(ListNode0,ListNode1);
107     ConnectListNodes(ListNode1,ListNode2);
108     ConnectListNodes(ListNode2,ListNode3);
109     ConnectListNodes(ListNode3,ListNode4);
110     ConnectListNodes(ListNode4,ListNode5);
111     ConnectListNodes(ListNode5,ListNode6);
112 
113     Test(ListNode0);
114     DestroyList(ListNode0);
115 }
116 
117 // 只有一个结点
118 void Test3()
119 {
120     cout<<"Test3 begins."<<endl;
121     Node* ListNode0=CreateListNode(0);
122     Test(ListNode0);
123     DestroyList(ListNode0);
124 }
125 
126 // 空链表
127 void Test4()
128 {
129     cout<<"Test4 begins."<<endl;
130     Test(NULL);
131 }
132 
133 int main()
134 {
135     Test1();
136     Test2();
137     Test3();
138     Test4();
139     return 0;
140 }

总结：1.离开了VS，自己手写并且能够写对还是很困难。
2.时间复杂度O(n²),应该还可以优化。

欢迎批评指正！