反向链表

Question

下面给出了两个反向链表的代码，第一个正确工作，第二个不正确。有人可以解释为什么会这样吗？

工作代码：

def rev(curr, prev):
    if not curr:
        return prev
    next = curr.next
    curr.next = prev
    prev = curr
    curr = next
    return rev(curr, prev)

无效代码：

def rev(curr, prev):
    if not curr:
        return prev
    # next = curr.next
    curr.next = prev
    # prev = curr
    # curr = next
    return rev(curr.next,curr)

I am calling both above function in this way :

rev(head,None)

输入：

1->2->3->4->None

第一个代码的输出：

4->3->2->1->None

第二个代码的输出：

1->None

第二个代码的期望输出：

4->3->2->1->None

Answer 1

在第二个代码中，您注释了将下一个指针分配给当前指针的行，而不是使用循环来迭代整个列表。这就是为什么它只显示列表的第一项。

您可以在下面的 link 中找到 linked 列表的视频动画，这有助于您理解反向 linked 列表的概念。

参考 Link : https://www.geeksforgeeks.org/reverse-a-linked-list/

代码：

class Node: 

    # Constructor to initialize the node object 
    def __init__(self, data): 
        self.data = data 
        self.next = None

class LinkedList: 

    # Function to initialize head 
    def __init__(self): 
        self.head = None

    # Function to reverse the linked list 
    def reverse(self): 
        prev = None
        current = self.head 
        while(current is not None): 
            next = current.next
            current.next = prev 
            prev = current 
            current = next
        self.head = prev 

    # Function to insert a new node at the beginning 
    def add(self, new_data): 
        new_node = Node(new_data) 
        new_node.next = self.head 
        self.head = new_node 

    # Utility function to print the linked LinkedList 
    def printList(self): 
        temp = self.head 
        while(temp): 
            print(temp.data) 
            temp = temp.next


# Driver program to test above functions 
llist = LinkedList() 
llist.add(20) 
llist.add(4) 
llist.add(15) 
llist.add(85) 

print("Given Linked List")
llist.printList() 
llist.reverse() 
print("\nReversed Linked List")
llist.printList()

输出：

Given Linked List                                                                                                       
85                                                                                                                      
15                                                                                                                      
4                                                                                                                       
20                                                                                                                      

Reversed Linked List                                                                                                    
20                                                                                                                      
4                                                                                                                       
15                                                                                                                      
85

Answer 2

您正在执行递归调用 return rev(curr.next,curr) 之后：

curr.next = prev

因此，在您的初始调用 rev(head, None) 中，您设置了 head.next = None，然后使用 None 调用 rev（并返回 head）。

更改为：

def rev(curr, prev):
    if not curr:
        return prev
    next = curr.next
    curr.next = prev
    return rev(next,curr)

反向链表

Reverse LinkedList

python

recursion

linked-list

singly-linked-list