NC2 题解 | #重排链表#

题意分析

• 给出一个链表，需要我们对这个链表进行重新排列，交错取出原来的链表最前面没有被取过的和最后面没有被取过的结点，新的链表就是按照这个取出的顺序重新拼接而成的一个链表。
• 样例解释
  

思路分析

• 题目的意思是给我们一个链表的头结点，需要我们不能改变结点内部的值，只能改变结点的next指针。这样的话，我们首先需要知道的就是将这个链表的所有的结点先进行保存，我们可以开一个动态数组vector，然后，我们使用双指针的方法一个l，一个r，用来表示当前最前面可以选择的结点的位置和当前最后面可以选择的结点的位置。这样的话我们就可以通过移动指针，然后不断更新每个结点的next结点。
  

写法一

• 代码如下
  • 需要遍历整个链表的所有的结点，时间复杂度为O(n)
  • 需要存储整个链表的所有的结点的值和指针，空间复杂度为O(n)

/**
 * 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;
        }
        vector<ListNode*> v;
        ListNode* now=head;
        // 将所有的结点先存入一个动态数组里面
        while(now){
            v.push_back(now);
            now=now->next;
        }
        // 定义动态数组的双指针，分别指向最前面的没被使用的结点和最后面没被使用的结点的位置
        int l=1,r=v.size()-1;
        now=head;
        int x=0;  // 我们定义一个x用来表示我们现在是取最前面的结点还是取后面的结点
        while(l<=r){
            if(x&1){
                now->next=v[l];
                l++;
            }else{
                now->next=v[r];
                r--;
            }
            now=now->next;
            x++;
        }
        // 最后记得把链表的最后的结点的next结点指向为NULL，不断会段错误
        now->next=NULL;
    }
};

写法二

• 如果对我上面的while循环感觉比较难理解的话，可以尝试使用下面的写法，就是我们先把前面取的指针和后面取的指针都放到不同的动态数组里面，然后对两个数组轮流取结点就可以了。这种写法的空间复杂度是一样的，就是切入点有一点不一样。

• 代码如下

  • 需要遍历整个链表的所有的结点，时间复杂度为O(n)
  • 需要存储整个链表，空间复杂度为O(n)

/**
 * 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;
        vector<ListNode*> pre,suf;  // pre表示取的前面的结点，suf表示取的后面的结点
        ListNode* now = head;
        while(now){  // 我们先将所有的结点都暂时存放到pre数组里面
            pre.push_back(now);
            now=now->next;
        }
        int x=pre.size(),mid=(x+1)/2;
        while(x>mid){  //然后我们将后半部分的节点存放到我们的suf数组里面
            suf.push_back(pre[x-1]);
            pre.pop_back();
            x--;
        }
        now=head;
        int len2=suf.size(),len1=pre.size();
        int l=1,r=0;
        // l指针表示的是当前的pre数组可以用的结点的位置，r指针表示的是的当前的suf数组可以用结点的位置
        while(l<len1||r<len2){
            if(l==r){
                now->next=pre[l];
                l++;
            }else{
                now->next=suf[r];
                r++;
            }
            now=now->next;
        }
        // 记得最后的节点的next指针指向NULL
        now->next=NULL;
    }
};