【面试题】重排单链表

今天刷的小题一道，微软14年校园招聘笔试唯一一道编程题。

Given a singly 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...).

1 struct Node  
2 {  
3     int val_;  
4     Node* next;  
5 };

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

代码：

 1 Node* ReorderList(Node* sll)
 2 {
 3     if(sll == NULL || sll->next == NULL || sll->next->next == NULL)
 4         return sll;
 5     Node* p1 = sll;
 6     Node* p2 = sll->next;
 7     Node* p3 = sll;
 8     Node* p4 = sll->next;
 9     while(p4->next != NULL)
10     {
11         p3 = p3->next;
12         p4 = p4->next;
13     }
14     while(p2->next != NULL)
15     {
16         p1->next = p4;
17         p4->next = p2;
18         p3->next = NULL;
19         p1 = p2;
20         p2 = p2->next;
21         p4 = sll;
22         while(p4->next != p3)
23             p4 = p4->next;
24         p3 = p4;
25         p4 = p4->next;
26         if(p2 == NULL)
27             break;
28     }
29     return sll;
30 }

View Code

自己多动手没坏处~

【面试题】重排单链表

推荐阅读