关于leetcode:完虐算法链表的奇偶重排

链表的奇偶重排

更多算法题解，请关注公众号【程序员学长】

问题形容

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)。