奇偶链表问题

奇偶,链表,问题 · 浏览次数 : 25

小编点评

```python class ListNode: def __init__(self, val=0, next=None, prev=None): self.val = val self.next = next self.prev = prev def oddEvenList(head): oddStart, oddEnd, evenStart, evenEnd = None, None, None, None count = 1 cur = head while cur: if (count & 1) == 1: if oddStart is None: oddStart = cur else: oddEnd.next = cur oddEnd = cur else: if evenStart is None: evenStart = cur else: evenEnd.next = cur evenEnd = cur count += 1 cur = cur.next if evenEnd: evenEnd.next = oddStart return oddStart ``` **代码解释：** 1. 使用四个指针 `oddStart`、`oddEnd`、`evenStart` 和 `evenEnd` 来记录奇数链表和偶数链表。 2. 遍历链表，并根据奇偶性构造链表。 3. 如果当前节点是奇数，则将 `oddStart` 指向当前节点，否则将 `oddEnd` 指向当前节点。 4. 如果当前节点是偶数，则将 `evenStart` 指向当前节点，否则将 `evenEnd` 指向当前节点。 5. 最后，将 `oddStart` 和 `evenStart` 的下一个指针指向 `oddEnd` 和 `evenEnd` 的前一个节点，即可构建最终的链表。 **时间复杂度：O(n)，其中 n 是链表的长度。** 这是因为我们只遍历链表一次，并使用四个指针来记录奇偶链表和偶数链表的信息。

正文

奇偶链表问题

作者：Grey

原文地址：

博客园：奇偶链表问题

CSDN：奇偶链表问题

题目描述

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

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

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

算法和数据结构笔记