Given a singly linked list L: L 0→L 1→…→L n-1→L n, reorder it to: L 0→L n →L 1→L n-1→L 2→L n-2→…
You must do this in-place without altering the nodes' values.
For example, Given{1,2,3,4}, reorder it to{1,4,2,3}.
C++
/** * 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) { if (!head || !head->next || !head->next->next) return; ListNode *fast = head; ListNode *slow = head; while (fast->next && fast->next->next) { slow = slow->next; fast = fast->next->next; } ListNode *mid = slow->next; slow->next = NULL; ListNode *last = mid; ListNode *pre = NULL; while (last) { ListNode *next = last->next; last->next = pre; pre = last; last = next; } while (head && pre) { ListNode *next = head->next; head->next = pre; pre = pre->next; head->next->next = next; head = next; } } };
转载于:https://www.cnblogs.com/vercont/p/10210255.html
相关资源：JAVA上百实例源码以及开源项目