乐趣区

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

退出移动版