[leetcode题解]328 Odd Even Linked List(python+c++)

题目给定一个包含数字的链表,要求把链表进行修改,保证奇数位置的元素按顺序排在前面,然后是偶数位置的元素一次排在后面。返回修改后的链表即可。
简单的思路就是把所有奇数位的元素摘出来按原有顺序组成一个链表even然后把所有偶数位置的元素摘出来组成一个新的链表odd,然后把odd链表链在even链表之后就可以了。这样能保证空间复杂度o(1),时间复杂度o(n)。如下为c++和python两个版本的代码。在python代码中,开始使用idx作为计数,然后通过除2来判断奇偶,运行时间68ms,然后把判断奇偶改成通过一个bool值来判断,python的性能提升一倍,32ms。

c++代码:

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) 
    {
        ListNode *odd = new ListNode(-1);
        ListNode *even = new ListNode(-1);
        
        ListNode *tailOdd = odd, *tailEven = even;
        
        ListNode *p = head;
        
        bool isOdd = true;
        while(p != NULL)
        {
            if (isOdd)
            {
                tailOdd->next = p;
                tailOdd = tailOdd->next;
                
            }
            else
            {
                tailEven->next = p;
                tailEven = tailEven->next;
            }
            isOdd = !isOdd;
            p = p->next;
        }
        
        tailOdd->next = even->next;
        tailEven->next = NULL;
        return odd->next;
    }
};

python代码:

class Solution(object):
    def oddEvenList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        even = ListNode(-1)
        odd = ListNode(-1)
        
        taile, tailo = even, odd
        
        isEven = True
        while head != None:
            t = head.next
            if isEven:
                taile.next = head
                taile = taile.next
                isEven = False
            else:
                tailo.next = head
                tailo = tailo.next
                isEven = True
            head = t
        taile.next = odd.next
        tailo.next = None
        return even.next

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]328 Odd Even Linked List(python+c++)

本文链接地址:http://www.iaccepted.net/algorithm/leetcode/50.html

相关文章



发表评论

电子邮件地址不会被公开。 必填项已用*标注