首页 > 其他 > 详细

【Reorder List】cpp

时间:2015-05-01 10:36:44      阅读:135      评论:0      收藏:0      [点我收藏+]

题目

Given a singly linked list LL0→L1→…→Ln-1→Ln,
reorder it to: L0→LnL1→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) return;
        ListNode dummy(-1);
        dummy.next = head;
        ListNode *p1 = &dummy, *p2 = &dummy;
        // get the mid Node
        for (; p2 && p2->next; p1 = p1->next, p2 = p2->next->next);
        // reverse the second half list
        for ( ListNode *prev = p1, *curr = p1->next; curr && curr->next; ){
            ListNode *tmp = curr->next;
            curr->next = curr->next->next;
            tmp->next = prev->next;
            prev->next = tmp;
        }
        // cut the list from mid and merge two list
        for ( p2 = p1->next, p1->next = NULL,p1 = head; p2; ){
            ListNode *tmp = p1->next;
            p1->next = p2;
            p2 = p2->next;
            p1->next->next = tmp;
            p1 = tmp;
        }
    }
};

Tips

改了两次,终于AC的效率进入5%了。

算法的思路:

Step1. 找到中间节点(p1指向中间节点之前的节点)

Step2. 把后半个List进行reverse操作

Step3. 讲两个Lists进行merge操作

尽量减少循环体中的无谓语句(例如条件判断语句、赋值语句、开新的中间变量),这样可以提升程序效率。

【Reorder List】cpp

原文:http://www.cnblogs.com/xbf9xbf/p/4470380.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!