更多题解，请关注公众号：程序员学长，让你进大厂不走弯路

链表的奇偶重排

问题描述

LeetCode 328. 奇偶链表

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

示例：

输入：{1，2，3，4，5，6}

输出：{1，3，5，2，4，6}

分析问题

要想把一个链表的奇数节点和偶数节点分别排在一起，我们可以先分离链表，把一个链表拆分成两个链表，其中一个是奇数链表，另一个是偶数链表，最后将偶数链表拼接在奇数链表后即可。

我们都知道，对于一个链表来说，相邻节点的奇偶性是不同的。原始链表的头节点head是奇数链表的头节点，head的后一个节点是偶数链表的头节点，我们假设是evenHead ，则evenHead = head.next。我们维护两个指针odd和even分别指向奇数链表和偶数链表的最后一个节点，初始时 odd=head，even=evenHead。通过不断的更新odd和even，将链表分割成奇数链表和偶数链表。

1. 更新奇数节点，我们令 odd.next=even.next，此时奇数链表的最后一个节点指向了偶数节点even的后一个节点。然后令odd=odd.next，此时odd变成了even的后一个节点。
2. 更新偶数节点，我们令 even.next=odd.next，此时偶数节点的最后一个节点指向了奇数节点odd的后一个节点。然后令even=even.next，此时even变成了odd的后一个节点。

通过以上两步，我们就完成了对一个奇数节点和一个偶数节点的分离。重复上述操作，直到全部节点分离完成。最后令 odd.next = evenHead，将偶数链表连接在奇数链表之后，即完成了奇数链表和偶数链表的合并。

下面我们来看一下代码的实现。

class Solution:
    def oddEvenList(self, head):
        #如果链表为空，直接返回
        if not head:
            return head
        #evenHead指向偶数链表的头节点
        evenHead = head.next
        #指向奇数链表和偶数链表的末尾节点
        odd = head
        even = evenHead
        while even and even.next:
            #奇数链表的末尾节点指向偶数节点的下一个节点
            odd.next = even.next
            #奇数链表末尾节点后移
            odd = odd.next
            #偶数链表的末尾节点指向奇数节点的下一个节点
            even.next = odd.next
            #偶数链表末尾节点后移
            even = even.next

        #偶数链表连接到奇数链表的末尾
        odd.next = evenHead
        return head

该算法的时间复杂度是O(n)，空间复杂度是O(1)。