reorder-list 重排链表

 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     void reorderList(ListNode *head) {
12         if(head == NULL)
13             return;
14         //快慢指针找到中间节点
15         ListNode* slow = head;
16         ListNode* fast = head;
17         while(fast->next != NULL && fast->next->next != NULL){
18             slow = slow->next;
19             fast = fast->next->next;
20         }
21         ListNode* l1 = head;
22         ListNode* l2 = slow->next;
23         slow->next = NULL;
24         //反转后半段链表
25         ListNode* newhead = new ListNode(NULL);
26         ListNode* pre = newhead;
27         while( l2 != NULL){
28             ListNode* temp = l2->next;
29             l2->next = pre->next;
30             pre->next = l2;
31             l2 = temp;
32         }
33         l2 = pre->next;
34         //合并两个链表
35         while( l2 != NULL ){
36             ListNode* l1_next = l1->next;
37             ListNode* l2_next = l2->next;
38             l1->next = l2;
39             l2->next = l1_next;
40             l1 = l1_next;
41             l2 = l2_next;
42         }
43     }
44 };