奇偶链表问题
题目描述
给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。
请尝试使用原地算法完成。
你的算法的空间复杂度应为 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
说明: 应当保持奇数节点和偶数节点的相对顺序。
链表的第一个节点视为奇数节点,第二个节点视为偶数节点,以此类推。
主要思路
如果用辅助数组来做,非常简单,但是不满足题目的要求,因为题目要求空间复杂度 O(1),意味着不能额外申请辅助数组,换一个思路,考虑用一个整型变量来记录遍历的位置是奇数还是偶数,然后用四个指针分别记录当前奇数链表的开头,结尾;偶数链表的开头和结尾,最后把两个链表串联起来即可,所以,只需要设置五个变量即可完成整个算法。
// 奇数链表的开头节点
ListNode oddStart = null;
// 奇数链表的结尾节点
ListNode oddEnd = null;
// 偶数链表的开头节点
ListNode evenStart = null;
// 偶数链表的结尾节点
ListNode evenEnd = null;
// 当前遍历到的节点
ListNode cur = head;
// 当前遍历到的位置,根据题目意思,从 1 开始
int count = 1;
整个流程如下,遍历 cur 指针,同步记录 count,如果 count 记录的位置是奇数, 则构造奇数链表,如果 count 位置记录的是偶数,则构造偶数链表。
构造的过程也比较简单,以构造奇数链表为例:
如果 oddStart
变量为空,则说明奇数链表未初始化,则直接初始化
oddStart = cur;
oddEnd = cur;
奇数链表的头尾指针都指向 cur,说明初始化完成;
否则,说明奇数链表已经初始化过,则把奇数链表的尾部的 next 直接连上 cur
,然后把奇数链表的尾部指针指向 cur
,即
oddEnd.next = cur;
oddEnd = cur;
构造偶数链表的过程和构造奇数链表的过程同理,不赘述。
构造好两个链表以后,把两个链表连接起来即可,连接的逻辑如下:
如果偶数链表尾部不为空,则奇数链表一定不为空,且偶数链表的尾部就是变换后链表的尾部,即
if (evenEnd != null) {
evenEnd.next = null;
}
最后,要把奇数链表尾部的 next 连接上偶数链表的头部
oddEnd.next = evenStart;
完整代码如下
class Solution {
// 奇数节点和偶数节点放在一起
// 所有偶数下标的数一定要在奇数下标数之后(注意:是下标而非值)
public static ListNode oddEvenList(ListNode head) {
if (head == null || head.next == null || head.next.next == null) {
return head;
}
ListNode oddStart = null;
ListNode oddEnd = null;
ListNode evenStart = null;
ListNode evenEnd = null;
ListNode cur = head;
int count = 1;
while (cur != null) {
if ((count & 1) == 1) {
// 奇数
if (oddStart == null) {
oddStart = cur;
} else {
oddEnd.next = cur;
}
oddEnd = cur;
} else {
// 偶数
if (evenStart == null) {
evenStart = cur;
} else {
evenEnd.next = cur;
}
evenEnd = cur;
}
count++;
cur = cur.next;
}
if (evenEnd != null) {
evenEnd.next = null;
}
oddEnd.next = evenStart;
return oddStart;
}
}