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}.
解答： 这道题分三步，第一步找到中点，通过走一步和走两步的方法找到链表中心。第二步，翻转后面的链表。第三步，把两个链表合起来。
/** * 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) return; ListNode*p1=head,*p2=head->next;//这里得是p2=head->next,而非head,否则[1,2]这个testcase过不了 while(p2&&p2->next) { p1=p1->next; p2=p2->next->next; } ListNode *head2=p1->next; p1->next=NULL; p2=head2->next; head2->next=NULL; while(p2) { p1=p2->next; p2->next=head2; head2=p2; p2=p1; } p2=head2; p1=head; ListNode* t=p1->next; while(p2) { p1->next=p2; p1=p2; p2=t; t=p1->next; } }};新闻热点
疑难解答
