遍历链表的函数

Question

class LN:
    def __init__(self,value,next=None):
        self.value = value
        self.next  = next
def list_to_ll(l):
    if l == []:
        return None
    front = rear = LN(l[0])
    for v in l[1:]:
        rear.next = LN(v)
        rear = rear.next
    return front
def add_after(ll,value,new):
    for item in ll:
        if item == value:
            ll.insert(ll.index(value),new)

我正在研究一个名为add_after的迭代函数。它接受链表和两个值，value和new。它会改变链表，使得每次出现值后都跟着new。例如:

a = list_to_ll([2,1,8,2,2,4,2,5,2])

add_after(a,2，-1)将指向一个包含值1->8->2->-1->4->2->-1->5->2->-1->None的链表。

add_after(a,2,2)对于a中的原始链表，结果指向一个包含值1->8->2->2->4->2->2->5->2->2->None的链表。

+(我不允许在我的代码中使用列表、元组、集合或字典)

使用链表只处理

当我运行add_after时，它给了我一个错误:

add_after(ll,2,-1)
for item in ll:
TypeError: 'LN' object is not iterable

谁能帮我修复我的add_after功能?多谢。

Answer 1

1. 通过定义产生节点的__iter__方法使LN可迭代:
让add_after链接新节点

---

class LN:
    def __init__(self, value, next=None):
        self.value = value
        self.next  = next
    def __iter__(self):  # yield all linked node (including the first node)
        node = self
        while node is not None:
            yield node
            node = node.next
def list_to_ll(l):
    if l == []:
        return None
    front = rear = LN(l[0])
    for v in l[1:]:
        rear.next = LN(v)
        rear = rear.next
    return front
def add_after(ll, value, new):
    for item in ll:
        if item.value == value:
            ll.next = LN(new, ll.next)  # Make new node and link after current node
            break
    # TODO: Handle not-found case.

ll = list_to_ll([2,1,8,2,2,4,2,5,2])
add_after(ll, 2, -1)
for item in ll:
    print(item.value)
# Prints 2, -1, 1, 8, 2, 2, 4, 2, 5, 2

---

UPDATE读取OP的注释后=>仅更改add_after(手动遍历节点):

def add_after(ll, value, new):
    node = ll
    while node is not None:
        if node.value == value:
            node.next = LN(new, node.next)
            break
        node = node.next

注意:我让add_after只添加一个节点。我将把它留给你的工作，以添加多个节点。

Answer 2

ll是用户自定义类LN的对象。它不像列表那样可迭代，因此for-each结构在此上下文中不起作用。

下面是另一种选择。

def add_after(ll,value,new):
    item = ll
    while item is not None:
        if item.value == value:
            newnode = LN(new, item.next)
            item.next = newnode
            break
        else:
            item = item.next

解决OP对在n处插入的关注，下面的代码也可以适用:

def add_after(ll,value,new,occ=1):
    item = ll
    while item is not None:
        if item.value == value:
            occ -= 1
            if occ == 0:
                newnode = LN(new, item.next)
                item.next = newnode
                break
        item = item.next

可选的第四个参数决定新值应该在出现之后插入。例如，add_after(ll, 2, -1, 2)在第二次出现2后加-1。

Answer 3

这是我使用递归的解决方案。我还添加了一个辅助方法flatten来可视化我在测试时的更改。

def add_after(ll, at_value, new_value):
    if ll.value == at_value:
        ll.next = LN(new_value, ll.next)
        if ll.next is not None and ll.next.next is not None:
            # skips over the newly added LN
            add_after(ll.next.next, at_value, new_value)
    elif ll.next is not None:
        add_after(ll.next, at_value, new_value)
def flatten(ll):
    if ll.next is None:
        return [ll.value]
    return [ll.value] + flatten(ll.next)
# Output
>>> a = list_to_ll([2,1,8,2,2,4,2,5,2])
>>> flatten(a)
[2, 1, 8, 2, 2, 4, 2, 5, 2]
>>> add_after(a, 2, -1)
>>> flatten(a)
[2, -1, 1, 8, 2, -1, 2, -1, 4, 2, -1, 5, 2, -1]
>>> b = list_to_ll([2,1,8,2,2,4,2,5,2])
>>> add_after(b, 2, 2)
>>> flatten(b)
[2, 2, 1, 8, 2, 2, 2, 2, 4, 2, 2, 5, 2, 2]