leetcode-328 奇偶链表-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode-328 奇偶链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目如下：
给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。
第一个节点的索引被认为是奇数，第二个节点的索引为偶数，以此类推。
请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。
你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。

示例如下：

leetcode-328 奇偶链表

输入: head = [1,2,3,4,5]
输出: [1,3,5,2,4]

提示:

n == 链表中的节点数
0 <= n <= 104
-106 <= Node.val <= 106

算法思路

官方题解我不知道它是怎么做的，反正我是这样做的。直接在在原链表head进行修改即可。
如果链表的节点的超过2个，那么把之后索引下标为奇数的节点连接在head的第一个节点后面(做完之后把对应的指针后移)，把索引下标为偶数的节点连接在head的第二个节点后面(做完之后把对应的指针后移)，直到到达最后一个节点即可。

图解如下(第5个元素没有画)：

leetcode-328 奇偶链表

实现代码如下(Python):

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
        
class Solution(object):
    def oddEvenList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        p = head
        count = 1
        p1 = None
        last = None
        while p:
            next = p.next
            p.next = None
            if count == 1:
                p1 = p
            elif count == 2:
                p1.next = p
                last = p1.next
            else:
                if count % 2 != 0:
                    p2 = p1.next
                    p1.next = p
                    p1 = p1.next
                    p1.next = p2
                else:
                    last.next = p
                    last = last.next

            p = next
            count += 1

        return head

if __name__ == '__main__':
    a = Solution()
    head = ListNode(1, ListNode(2,ListNode(3, ListNode(4,ListNode(5,None)))))
    a.oddEvenList(head)