奇數偶數鏈表

Question

我看到像本文給出了一個問題：

Given 1->2->3->4->5->NULL, 
return 1->3->5->2->4->NULL. 

我寫道：

class Solution(object): 
    def oddEvenList(self, head): 
     oddhead = head 
     evenhead = head.next 
     even = evenhead 
     while evenhead and evenhead.next : 
      oddhead.next = evenhead.next 
      oddhead.next = oddhead 
      evenhead.next = oddhead.next 
      evenhead.next = evenhead 
     oddhead.next = even 
     return head 

但它說time limit exceed.

我見過這樣一個人的解決方案：

class Solution(object): 
def oddEvenList(self, head): 
    odd, p= head, head and head.next 
    while p and p.next: 
     odd.next, p.next.next, p.next = p.next, odd.next, p.next.next #insert 
     odd, p = odd.next, p.next 
    return head 

任何人都可以請求se解釋爲什麼我的代碼在時間限制上失敗了？

對於解決方案，任何人都可以指出該代碼如何在特定的工作？我真的不太明白。

在此先感謝！

Answer 1

任何人都可以請解釋爲什麼我的代碼是在時間限制失敗？

在while循環你從來沒有修改evenhead，從而evenhead停留在節點2永遠和循環永遠不會終止。當然你的意思是有任務

  oddhead.next = oddhead 
      … 
      evenhead.next = evenhead 

倒過來：

  oddhead = oddhead.next 
      … 
      evenhead = evenhead.next 

- 這樣一來你的代碼工作。

對於解決方案，任何人都可以指出該代碼在 特定工作如何？

該解決方案基本上是一樣的你 - 這odd相當於你oddhead，p相當於evenhead，名單分配

 odd.next, … p.next = p.next, … p.next.next #insert 

等同於你（修正同上）

  oddhead.next = evenhead.next 
      oddhead = oddhead.next 
      evenhead.next = oddhead.next 

和清單分配

 odd, p = odd.next, p.next 

等同於你（如上校正）

  oddhead = oddhead.next 
      … 
      evenhead = evenhead.next 

- 一個區別在於分配

 … p.next.next… = … odd.next… #insert 

在循環

，當你前後分別有

 even = evenhead 
     … 
     oddhead.next = even 

循環;這相當於將臨時最後一個奇數節點鏈接到每個循環遍中的第一個偶數節點，而不是將最後找到的最後一個奇數節點鏈接到第一個偶數節點，僅在循環之後一次，後者似乎更有效。

其他解決方案比您的解決方案的唯一優點是它由於額外的測試head and head.next優雅地處理空列表（Solution().oddEvenList(None)）。