奇偶链表问题

题目描述

给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。

请尝试使用原地算法完成。

你的算法的空间复杂度应为 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;
    }
}

更多

算法和数据结构笔记