导航
导航
文章目录
  1. 题目
  2. 翻译
    1. 方法一
    2. 方法二

LeetCode-328.Odd Even Linked List

题目

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example:
Given 1->2->3->4->5->NULL,
return 1->3->5->2->4->NULL.

翻译

给出一个单链表,将所有的奇数节点放在偶数节点前面。注意这里说的是节点排序数而不是节点的值。
要求原地操作。程序空间复杂度应为O(1),时间复杂度为O(nodes)。
例如:
给出 1->2->3->4->5->NULL,
返回 1->3->5->2->4->NULL.

方法一

考虑替换值,可以遍历链表得出链表长度,然后新建一个相同长度的数组,再次遍历链表,将值储存在数组里,最后遍历,依次取出数组中存储的奇数位置和偶数位置的值,替换链表值。但空间复杂度与时间复杂度都是O(nodes)。

方法二

思路是将所有奇数节点串成一个单链表,所有偶数节点串成一个单链表,最后将奇数节点链表的尾与偶数节点链表的头连接起来即可。
首先设立一个指向第二个节点的指针evenHead,保存偶数节点链表的头。
设立两个指针,一个指向奇数节点odd,和一个指向下一个相邻的偶数节点even。
每次循环,使odd的next指到下一个奇数节点(即even的next),更新odd为下一个奇数节点,even的next指向下一个偶数节点(即odd的next),更新even为下一个偶数节点,一轮循环结束。当even为空(共奇数个节点)或even.next为空(共偶数个节点)时,停止循环。
此时奇数节点链表和偶数节点链表均已就绪,只要将奇数节点链表的尾(odd.next)指向偶数节点链表的头(even)即可:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode oddEvenList(ListNode head) {
if (head == null)
return head;

ListNode odd = head, even = head.next, evenHead = head.next;
while (even != null && even.next != null) {
odd.next = even.next;
odd = even.next;
even.next = odd.next;
even = odd.next;
}
odd.next = evenHead;

return head;
}
}