Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
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
Given
{1,2,3,4}
, reorder it to {1,4,2,3}
./** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: void reorderList(ListNode *head) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. // Get the List len. if (head == NULL) { return; } ListNode *tmp = head; int len = 0; while (tmp != NULL) { tmp = tmp->next; ++len; } int num_insertion = (len-1)/2; // Find the start of second half. tmp = head; int count = 0; while (count < len-1-num_insertion) { tmp = tmp->next; ++count; } ListNode *second_half = tmp->next; tmp->next= NULL; // Reverse the second half of the List. if (second_half != NULL && second_half->next != NULL) { ListNode * temp1 = second_half->next; second_half->next = NULL; while (temp1 != NULL) { ListNode *temp2 = temp1->next; temp1->next = second_half; second_half = temp1; temp1 = temp2; } } // Insert second half to first half. ListNode *first_half = head; while (second_half != NULL) { ListNode *temp1 = second_half->next; second_half->next = first_half->next; first_half->next = second_half; second_half = temp1; first_half = first_half->next->next; } } };
No comments:
Post a Comment