问题描述

单链表 面试题 互换元素

单链表 1 2 3 4 ... n-1 n，变成1 n 3 n-2 ....4 n-1 2，Java如何实现

解决方案

你的互换没有规律啊
比如说n=9
原来是 1 2 3 4 5 6 7 8 9
1 9 3 7 ... 4 8 2
5和6怎么排？

解决方案二：

看上去是间隔交换，2,4,6.。。交换

解决方案三：

按顺序遍历，奇数位不变，偶数为变为n-(x-2)，其中n为原数列中的n，x为当前遍历的序号。

解决方案四：

好吧，首先我想你问的问题并不是真的整数1 2 3...而是下标为1，2，3的数组进行重排，否则答案像autocyz给的，太，简单了。
其实你得先理解题意，1...n,你得知道n是奇数还是偶数，否则会得到错误的结论，如果是偶数，得到oyljerry的结论。是奇数，这里会会像caozhy说的一样，没有规律。哈哈。所以问过面试官，确认是偶数先（面试需要多问问题，明确考官的真实意图，也反映你的确在思考问题）
最后因为是面试题，你先考虑面试的要素，1.算法复杂度最低，一般来说o(1)最好，但是这个题目O(1)只有作弊，采用一个数据结构可以做到，O(n)是其次，一般面试题的正解都是O(n)算法。这个题目有O(n)解.这里考虑到是单链表，所以o(N）算法是你需要的，你可以考虑一下
1. 怎么在o(n)算法头尾交换，其实就是倒排，这个我想也不难对你，就是另外建一个链表，找到一个插入到链表头
2. 怎么只做偶数部分，其实也不复杂，2个指针，一个奇数指针，它读到的按原顺序写入一个奇数链表，一个偶数指针，利用1里面写入一个倒排的链表
3. 现在你有2个链表，按照两两合并弄成一个指针
我们看看复杂度：
1. 时间复杂度， 读第一次，得到2个新指针，一次遍历,n个操作，第二次，合并，n个操作，就是2n，复杂度仍然是O(N)
2. 空间复杂度，只要一个新链表，4个指针，N+4个指针大小
另外也许面试官会问：你能做到IN-place么，你理解一下in-place是什么意思，其实时间复杂度不会改变，而空间复杂度是4个指针。

解决方案五：

好吧，首先我想你问的问题并不是真的整数1 2 3...而是下标为1，2，3的数组进行重排，否则答案像autocyz给的，太，简单了。
其实你得先理解题意，1...n,你得知道n是奇数还是偶数，否则会得到错误的结论，如果是偶数，得到oyljerry的结论。是奇数，这里会会像caozhy说的一样，没有规律。哈哈。所以问过面试官，确认是偶数先（面试需要多问问题，明确考官的真实意图，也反映你的确在思考问题）
最后因为是面试题，你先考虑面试的要素，1.算法复杂度最低，一般来说o(1)最好，但是这个题目O(1)只有作弊，采用一个数据结构可以做到，O(n)是其次，一般面试题的正解都是O(n)算法。这个题目有O(n)解.这里考虑到是单链表，所以o(N）算法是你需要的，你可以考虑一下
1. 怎么在o(n)算法头尾交换，其实就是倒排，这个我想也不难对你，就是另外建一个链表，找到一个插入到链表头
2. 怎么只做偶数部分，其实也不复杂，2个指针，一个奇数指针，它读到的按原顺序写入一个奇数链表，一个偶数指针，利用1里面写入一个倒排的链表
3. 现在你有2个链表，按照两两合并弄成一个指针
我们看看复杂度：
1. 时间复杂度， 读第一次，得到2个新指针，一次遍历,n个操作，第二次，合并，n个操作，就是2n，复杂度仍然是O(N)
2. 空间复杂度，只要一个新链表，4个指针，N+4个指针大小。
另外也许面试官会问：你能做到IN-place么，你理解一下in-place是什么意思，其实时间复杂度不会改变，而空间复杂度是4个指针