首页 > 代码库 > LeetCode "Reorder List"
LeetCode "Reorder List"
Not very hard to figure out the solution: splitting the list into 2 halves; reverse the 2nd half and interleave the two halves.
But it takes some time to code due to a lot of details - majority of them are boudary conditions.
class Solution {public: ListNode *findHalf(ListNode *p) { ListNode dummy(0); dummy.next = p; ListNode *sp = &dummy; ListNode *fp = &dummy; bool bOdd = false; ListNode *toCut = NULL; while(fp) { toCut = sp; sp = sp->next; fp = fp->next; if(fp) fp = fp->next; else bOdd = true; } if(bOdd) { toCut->next = NULL; return sp; } else { ListNode *tmp = sp->next; sp->next = NULL; return tmp; } } ListNode * interleave(ListNode *p0, ListNode *p1) { ListNode *pa = p0; ListNode *pb = pa->next; ListNode *pc = p1; ListNode *pd = pc->next; while(pa && pc) { pa->next = pc; pc->next = pb; pa = pb; if(pb) pb = pb->next; pc = pd; if(pd) pd = pd->next; } return p0; } ListNode *reverseList(ListNode *p) { if(!p->next) return p; ListNode *p0 = NULL; ListNode *p1 = p; ListNode *p2 = p->next; // Reverse while(p1) { p1->next = p0; p0 = p1; p1 = p2; if(p2) p2 = p2->next; } return p0; } void reorderList(ListNode *head) { if(!head || !head->next) return; ListNode *p1 = findHalf(head); p1 = reverseList(p1); interleave(head, p1); }};
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。