Given a singly linked list L: L0→L1→…→Ln-1→Ln,
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 {1,2,3,4}
, reorder it to {1,4,2,3}
.
思路:本题未限制额外的space,所以可先得到该转换的节点,将该节点之后的节点存储在栈中,即可实现之后节点的反转。
/** * 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) { stack<ListNode*> S; ListNode* ptr = head; ListNode* top; ListNode* previous; int n = 0; while(ptr != NULL) { ++n; ptr = ptr->next; } if (n == 1 || n == 2 || n == 0) { return; } n = n/2 + n%2; ptr = head; while(n--) { ptr = ptr->next; } while(ptr != NULL) { S.push(ptr); ptr = ptr->next; } previous = head; while(!S.empty()) { top = S.top(); S.pop(); ptr = previous->next; previous->next = top; top->next = ptr; previous = ptr; } previous->next = NULL; } };