一个包含 n 个元素的线性链表:

L = (a1, a2, …, an-2, an-1, an)

现在要对其中的结点进行重新排序,得到一个新链表:

L' = (a1, an, a2, an-1, a3, an-2, …)

样例1

输入:1->2->3->4
输出:1->4->2->3

样例2

输入:1->2->3->4->5
输出:1->5->2->4->3

数据范围

  • 1 ≤ n ≤ 1000
  • 1 ≤ ai ≤ 10000

题目分析

因为笔试要求空间O(1),故使用迭代的方式来解决。 如不考虑空间复杂度的话,可以考虑使用回溯算法,即先递归到链表末元素,回溯时再进行merge操作。

代码实现

迭代

 /*
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void rev(ListNode*& prev, ListNode*& fir) {
        while(fir->next) {
            auto ne = fir->next;
            fir->next = prev;
            prev = fir;
            fir = ne;    
        }
        fir->next = prev;
    }
    void rearrangedList(ListNode* head) {
        int cnt = 0;
        for (auto i = head; i; i = i->next) ++cnt;
        if (cnt == 1) return ;
        cnt = (cnt >> 1);
        auto sec = head;
        while(cnt--) sec = sec->next;
        auto ft = sec;
        sec = sec->next;
        ft->next = 0;

        // reverse from sec to end;
        auto prev = (ListNode*)0;
        rev(prev,sec);

        // merge
        while(sec) {
            auto fne = head->next;
            head->next = sec;
            auto sne = sec->next;
            sec->next = fne;
            sec = sne;
            head = fne;
        }
    }
}; 
分类: ListNodeThought

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status