迭代地組合鏈表

我正在嘗試迭代地組合兩個鏈接列表，但是我現在正在給我的結果相反。有沒有辦法按正確的順序組合列表，而不必在創建結果列表之後進行反轉？迭代地組合鏈表

class Link: 
    empty =() 

    def __init__(self, first, rest=empty): 
     assert rest is Link.empty or isinstance(rest, Link) 
     self.first = first 
     self.rest = rest 

    def __add__(self, lst): 
     """ 
     >>>s = Link(1, Link(2)) 
     >>>s + Link(3,Link(4)) 
     Link(1,Link(2,Link(3,Link(4)))) 
     """ 
     result = Link.empty 
     while self is not Link.empty: 
      result = Link(self.first,result) 
      self = self.rest 

     while lst is not Link.empty: 
      result = Link(lst.first, result) 
      lst = lst.rest 
     return result

來源

2016-03-07 stack_user_1156

看起來你已經創建了一個堆棧。 :) – erip

你的列表是不可變的嗎？這很重要，因爲不可變列表允許您採取一些快捷方式（例如，重用列表的一部分），如果列表可能被其他代碼修改，則不能執行此操作）。 – Blckknght

避免更改self，找到的第一個列表的末尾，而第二列表添加到它。

def __add__(self, lst): 
    current = self 

    while current.rest != self.empty: 
     current = current.rest 

    current.rest = lst 

    return self

或者，如果你喜歡返回一個新的鏈接列表：

def __add__(self, lst): 
    new_list = Link(self.first) 
    new_link = new_list 

    current = self 

    while current.rest != self.empty: 
     new_link.rest = Link(current.first) 
     new_link = new_link.rest 

     current = current.rest 

    current = lst 

    while current != self.empty: 
     new_link.rest = Link(current.first) 
     new_link = new_link.rest 

     current = current.rest 

    return new_list

注：這會讓每個Link.first值（不是獨立的副本）引用。

來源

2016-03-07 02:05:22 MattMS

從概念上講，兩個鏈表合併，所有你需要做的是找到的第一個列表的尾，並將其與第二個列表的頭連接，然後返回第一個列表的頭。目前的代碼的主要問題是，你不保留在第一個列表的頭部。

我假設你想要的__add__方法來創建高達self隨後lst製作的拷貝，所以僅僅從self先lst創建Link S的副本，並附上他們爲你迭代。像這樣：

def __add__(self, lst): 
    result = Link(self.first) 
    cur = result 
    self = self.rest 
    # Copy our list 
    while self is not Link.empty: 
     cur.rest = Link(self.first) 
     cur = cur.rest 
     self = self.rest 
    # Copy and connect the Links in lst 
    while lst is not Link.empty: 
     cur.rest = Link(lst.first) 
     cur = cur.rest 
     lst = lst.rest 
    return result

要診斷當前代碼出了什麼問題，可以考慮一下例子。假設self是Link(1,Link(2))。

result = Link.empty 
    while self is not Link.empty: 
     result = Link(self.first,result)

什麼是result現在呢？

Link(self.first,result)
是Link(1, Link.empty)
```
self = self.rest 
```

現在self是Link(2,())

 result = Link(self.first,result)

什麼result現在？

Link(self.first,result)
是Link(2, Link(1, Link.empty))

糟糕。發現問題;您正在反向連接鏈接。

來源

2016-03-07 02:06:13 congusbongus

迭代地組合鏈表

回答

相關問題