链表的奇偶重排

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

问题形容

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