题目：重排链表

描述：将给定的单链表 L：L0→L1→…→Ln−1→Ln重新排序为：L0→Ln→L1→Ln−1→L2→Ln−2→…L_0→L_n要求使用原地算法，不能只改变节点内部的值，需要对实际的节点进行交换。

示例1：输入：{1,2,3,4}，返回值：{1,4,2,3}

说明：给定head链表1->2->3->4,重新排列为1->4->2->3,会取head链表里面的值打印输出

解法一：

思路分析：我们可以使用快慢指针的方法来解决该问题，首先将链表一分为二，将第二部分反转，反转的这一步非常重要，最后将两个链表连接起来，在使用快慢指针将链表分成两段的情况下，采用这种方式会导致链表结点个数为奇数的情况下，后半段比前半段多一个，前半段一结束，后半段就开始，所以在第三部分将两个链表连接起来的时候，要注意后半段是否结束，如果没有，则连接上剩余部分即可。

实例分析：输入：{1,2,3,4}

首先将链表反转以后就是{4,3,2,1}，将链表按照规律重新赋值一次，将链表反转后重新连接起来。

1—2—3—4

4—3—2—1

重新连接起来就是1—4—2—3—3—2—4—1

具体如下图所示：

若是，结点的值都不相同，则当遇到相同时，就断开，首先统计结点个数，然后判断终止条件，这样就需要重新建一个链表，将链表一分为二，反转后半段，重新连接。反转以后，要在新的链表结尾加上next=NULL。

其具体C++程序如下所示： 


/**
 * 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 == NULL || head->next == NULL)
             return;
         //分成两段
         ListNode *preSlow = NULL;//设置一个初始链表
         ListNode *slow = head,*fast = head;//分别设置快慢指针
         while(fast && fast->next)//循环停止条件
         {
             preSlow = slow;
             slow = slow->next;
             fast = fast->next->next;
         }  
         preSlow->next = NULL; //前半段
         //反转后半段
         ListNode *newBeg = slow;
         ListNode *last = newBeg->next;
         while(last)
         {
             ListNode *temp = last->next;
             last->next = newBeg;
             newBeg = last;
             last = temp;
         }
         slow->next = NULL;
         //合并
         fast = head;
         preSlow = NULL;
         while(fast)//以前半段为条件
         {
             ListNode *tem = newBeg->next;
             newBeg->next = fast->next;
             fast->next = newBeg;
             fast = newBeg->next;
             preSlow = newBeg;
             newBeg = tem;
         }
         if(newBeg != NULL)   //因节点个数为奇数时，后段比前段多一个，所以最后要判断
             preSlow->next = newBeg;
     }
};

重排链表在该程序中要不断循环链表值来进行判断，在原链表的基础上进行排列，故时间复杂度为O(N)，空间复杂度为O(N)。

解法二：

思路分析：首先我们将链表存储到一个ArrayList当中，利用双指针一个指向前面，一个指向后面，依次进行按题目要求的访问，最终将链表形式输出。
实例分析：输入：{1,2,3,4}

1、首先创建一个空的链表对象，将原链表内的所有元素都添加到新的链表当中：

链表对象

1

2

3

4

2、设置两个指针分别指向队首和队尾元素

链表对象

1

2

3

4

 

i

 

 

j

3、循环判断条件为i始终小于j，令i的下一个元素直接指向j，然后进行判断i与j是否相等，不相等的话，就令j继续指向i++所指的元素，第一轮判断结束。

链表对象

1

4

2

 

4、最后一轮循环，让元素2指向3，最后将结尾指向null即可。

链表对象

1

4

2

3

null

5、最终返回链表结果即可。

Java代码如下所示： 


import java.util.*;
import java.util.List;
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public void reorderList(ListNode head) {
        if(head == null)
            return ;
        Listlist = new ArrayList<>();
        while(head != null){//将元素添加到链表当中
            list.add(head);
            head = head.next;
        }
        //设置两个指针
        int i = 0;
        int j = list.size() - 1;
        while(i < j){ //前面的结点指向最后的结点 
            list.get(i).next = list.get(j);//1-4 
            i++; 
            if(i == j) 
                break; 
            list.get(j).next = list.get(i);//4-2     
            j--; 
        } 
        list.get(i).next = null;//最后一个节点的下一个节点为null 
    }     
}


因为要将链表的所有值都访问一次，所以其时间复杂度为O(N)，只有两个指针变量。其空间复杂度为O(1)。