Skip to content

328 odd even linked list

328. Odd Even Linked List

题目: https://leetcode.com/problems/odd-even-linked-list/

难度:

Medium

想法:因为相对顺序保持不变,所以可以拆list,然后再组合在一起?这样是满足题目要求的,因为linked list不像array,我们操作的时候只是用指向,没有分配新的空间。


class Solution(object):
    def oddEvenList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head == None or head.next == None or head.next.next == None:
            return head

        oddDummy = ListNode(-1)
        oddDummy.next = head

        evenDummy = ListNode(-1)
        evenDummy.next = head.next

        oddCur = oddDummy.next
        evenCur = evenDummy.next

        cur = head.next.next
        while cur:
            oddCur.next = cur
            oddCur = oddCur.next
            evenCur.next = cur.next
            evenCur = evenCur.next
            if cur.next:
                cur = cur.next.next 
            else:
                cur = cur.next
        oddCur.next = evenDummy.next
        # print oddDummy.next.val
        return oddDummy.next

看别人的优雅代码

class Solution(object):
    def oddEvenList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head == None:
            return head

        # odd used to keep track of the tail of odd nodes
        odd = oddHead = head
        # record how many swaps happend
        even = evenHead = head.next
        while even and even.next:
            odd.next = even.next
            odd = odd.next
            even.next = odd.next 
            even = even.next
        odd.next = evenHead
        return head 

intuitive and concise

1 → 2 → 3 → 4 → 5 → NULL

一开始

 1    → 2     → 3 →    4    → 5    → NULL
odd   even     even.next


1 → 3  →    4    → 5    → NULL
    odd     ↑
    2   -   


1 → 3  →    4    → 5    → NULL
    odd     
    2   -   even


再loop一次:

            |   -----------  
    |   ---------  ↓       ↓
1 → 3       4      5    → NULL
                 odd       ↑
    2   -   ↑              even


最后一步,再将两个odd的最后一个和evenHead连接起来,完工


回到顶部