LeetCode328_奇偶链表

2019-12-04

用python语言解答LeetCode的328题

解题思路：
把奇节点放在一个链表里，偶节点放在另一个链表里，最后把偶链表接在奇链表的尾部

算法实现：
一个LinkedList需要一个头指针和一个尾指针来支持双端操作。

我们用变量head和odd保存奇数链表的头和尾指针。

evenHead和even保存偶链表的头和尾指针。
算法会遍历原链表一次并把奇节点放到奇数链表中去，偶节点放到偶链表中去。

遍历整个链表我们至少需要一个指针作为迭代器。这里odd指针和even不仅仅是尾指针，也可以扮演原链表迭代器的角色。

解决链表问题最好的办法就是在脑中或者纸上把链表画出来！！！

avatar

代码实现：


    #coding:utf-8

    class ListNode:
        def __init__(self, val):
            self.val = val
            self.next = next

    class Solution:
        def oddEvenList(self, head):
            if not head:
                return head
            p = head
            t = q = p.next
            while p and p.next and q and q.next:
                p.next, q.next = p.next.next, q.next.next
                p, q = p.next, q.next

            p.next = t
            return head