请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)时间复杂度应为 O(nodes)nodes 为节点总数。
示例 1:
输入: 1->2->3->4->5->NULL 输出: 1->3->5->2->4->NULL 示例 2:
输入: 2->1->3->5->6->4->7->NULL 输出: 2->3->6->7->1->5->4->NULL 说明:
应当保持奇数节点和偶数节点的相对顺序。 链表的第一个节点视为奇数节点第二个节点视为偶数节点以此类推。
解法
如果链表为空则直接返回链表。
对于原始链表每个节点都是奇数节点或偶数节点。头节点是奇数节点头节点的后一个节点是偶数节点相邻节点的奇偶性不同。因此可以将奇数节点和偶数节点分离成奇数链表和偶数链表然后将偶数链表连接在奇数链表之后合并后的链表即为结果链表。
原始链表的头节点 head 也是奇数链表的头节点以及结果链表的头节点head 的后一个节点是偶数链表的头节点。令 evenHead head.next则 evenHead 是偶数链表的头节点。
维护两个指针 odd 和 even 分别指向奇数节点和偶数节点初始时 odd headeven evenHead。通过迭代的方式将奇数节点和偶数节点分离成两个链表每一步首先更新奇数节点然后更新偶数节点。
更新奇数节点时奇数节点的后一个节点需要指向偶数节点的后一个节点因此令 odd.next even.next然后令 odd odd.next此时 odd 变成 even 的后一个节点。
更新偶数节点时偶数节点的后一个节点需要指向奇数节点的后一个节点因此令 even.next odd.next然后令 even even.next此时 even 变成 odd 的后一个节点。
在上述操作之后即完成了对一个奇数节点和一个偶数节点的分离。重复上述操作直到全部节点分离完毕。全部节点分离完毕的条件是 even 为空节点或者 even.next 为空节点此时 odd 指向最后一个奇数节点即奇数链表的最后一个节点。
最后令 odd.next evenHead将偶数链表连接在奇数链表之后即完成了奇数链表和偶数链表的合并结果链表的头节点仍然是 head。 
public ListNode oddEvenList(ListNode head) {if (head null) {return head;}ListNode evenHead head.next;ListNode odd head;ListNode even head.next;while (even ! null null) {odd.next even.next;odd odd.next;even.next odd.next;even even.next;}odd.next evenHead;return head;}
61.旋转链表
61. 旋转链表 给定一个链表旋转链表将链表每个节点向右移动 k 个位置其中 k 是非负数。
示例 1:
输入: 1->2->3->4->5->NULL, k 2 输出: 4->5->1->2->3->NULL 解释: 向右旋转 1 步: 5->1->2->3->4->NULL 向右旋转 2 步: 4->5->1->2->3->NULL 示例 2:
输入: 0->1->2->NULL, k 4 输出: 2->0->1->NULL 解释: 向右旋转 1 步: 2->0->1->NULL 向右旋转 2 步: 1->2->0->NULL 向右旋转 3 步: 0->1->2->NULL 向右旋转 4 步: 2->0->1->NULL
来源力扣LeetCode 链接https://leetcode-cn.com/problems/rotate-list 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
解法
【双指针】首尾相连形成环在中间断开
这题k是非负数但k有可能比链表的长度还要大所以先要计算链表的长度len需要旋转的步数就是k%len。一种比较简单的方式就是先把链表连接成一个环然后再把链表在某个合适的位置断开。
我们可以使用两个指针一个快指针fast从头开始遍历直到走到链表的末尾然后再把链表串成一个环形。还一个指针slow也是从头开始走len-k%len步就是我们要返回的链表头这里可能有点疑问为什么不是走k%len步这是因为我们需要把链表后面的k%len个移到前面因为单向链表我们没法从后往前遍历所以我们只能从前往后移动len-k%len步。但实际上操作的时候会少走一步具体来举个例子看一下这里就以示例1为例画个图来看一下 
public ListNode rotateRight(ListNode head, int k) {if (head null || head.next null) {return head;}ListNode fast head;ListNode slow head;int len 1;// 统计链表的长度顺便找到链表的尾结点while (fast.next ! null) {fast fast.next;len;}// 首尾相连先构成环fast.next head;// 计算慢指针移动的步数 并使slow指向旋转之后的尾节点int step len - k % len;while (step-- > 1) {slow slow.next;}// temp就是需要返回的结点,断开slow指针ListNode temp slow.next;slow.next null;return temp;}
86. 分隔链表
题目
86. 分隔链表 面试题 02.04. 分割链表 给你一个链表和一个特定值 x 请你对链表进行分隔使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例
输入head 1->4->3->2->5->2, x 3 输出1->2->2->4->3->5
解法
直观来说我们只需维护两个链表small 和large 即可small 链表按顺序存储所有小于 x 的节点large 链表按顺序存储所有大于等于 x 的节点。遍历完原链表后我们只要将small 链表尾节点指向 large 链表的头节点即能完成对链表的分隔。
为了实现上述思路我们设 smallHead 和 largeHead 分别为两个链表的哑节点即它们的next 指针指向链表的头节点这样做的目的是为了更方便地处理头节点为空的边界条件。同时设 small 和 large 节点指向当前链表的末尾节点。开始时 smallHeadsmall,largeHeadlarge。随后从前往后遍历链表判断当前链表的节点值是否小于 x如果小于就将small 的 next 指针指向该节点否则将 large 的 next 指针指向该节点。
遍历结束后我们将 large 的next 指针置空这是因为当前节点复用的是原链表的节点而其 next 指针可能指向一个小于 x 的节点我们需要切断这个引用。同时将small 的next 指针指向largeHead 的next 指针指向的节点即真正意义上的large 链表的头节点。最后返回 smallHead 的next 指针即为我们要求的答案。
public ListNode partition(ListNode head, int x) {// 指向较小链表的哑结点ListNode dummySmall new ListNode(-1);ListNode small dummySmall;// 指向较大链表的哑结点ListNode dummyLarge new ListNode(-1);ListNode large dummyLarge;// 如果当前值小于x,则将小链表指向它。否则将大链表指向它。while (head ! null) {if (head.val < x) {small.next head;small small.next;} else {large.next head;large large.next;}head head.next;}// 将两个链表拼接起来大链表尾部置空large.next null;small.next dummyLarge.next;return dummySmall.next;}
725.分隔链表
题目
725. 分隔链表
给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。
每部分的长度应该尽可能的相等: 任意两部分的长度差距不能超过 1也就是说可能有些部分为 null。
这k个部分应该按照在链表中出现的顺序进行输出并且排在前面的部分的长度应该大于或等于后面的长度。
返回一个符合上述规则的链表的列表。
举例 1->2->3->4, k 5 // 5 结果 [ [1], [2], [3], [4], null ]
示例 1
输入: root [1, 2, 3], k 5 输出: [[1],[2],[3],[],[]] 解释: 输入输出各部分都应该是链表而不是数组。 例如, 输入的结点 root 的 val 1, root.next.val 2, \root.next.next.val 3, 且 root.next.next.next null。 第一个输出 output[0] 是 output[0].val 1, output[0].next null。 最后一个元素 output[4] 为 null, 它代表了最后一个部分为空链表。
示例 2
输入: root [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k 3 输出: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]] 解释: 输入被分成了几个连续的部分并且每部分的长度相差不超过1.前面部分的长度大于等于后面部分的长度。
解法
如果链表有 N 个结点则分隔的链表中每个部分中都有 n/k 个结点且前 N%k 部分有一个额外的结点。我们可以用一个简单的循环来计算 N。 现在对于每个部分我们已经计算出该部分有多少个节点width (i
public ListNode[] splitListToParts(ListNode root, int k) {// 计算链表长度int len 0;ListNode cur root;while (cur ! null) {len;cur cur.next;}// 每个子链表中应该有的节点个数int width len / k;// 有几个子链表应该多存一个节点int rem len % k;// pre节点为哑结点方便删除ListNode pre null;cur root;ListNode[] ans new ListNode[k];// 遍历k组子节点 每次rem-1,表面要多存1个的子链表在减少for (int i 0; i 0 ? 1 : 0);for (int j 0; j < part_len; j) {pre cur;cur cur.next;}// pre有可能为空if (pre ! null) {pre.next null;}}return ans;}【本文由： 阜宁网站制作公司 http://www.1234xp.com/funing.html 欢迎留下您的宝贵建议】