数据结构单链表

Question

假设我在单链表中有一个头指针 H，我将如何用伪代码实现这一点？ 将H指向的单链表中的节点反转。注意：不能添加新节点 创建的。

Answer 1

可以递归地解决，将问题拆分为第一个节点和其余节点，将其余节点反转，然后将新的最后一个节点指向第一个节点。递归堆栈的每个级别都从调用它的级别的“其余”节点开始

reverse(node header){

//Return if empty list.
if (h == null) return

//Split the problem into first and rest.
node first = header.start
node rest = first.next

//Return if only one node.
if (rest == null) return

//reverse the rest of the problem, and then point the end of the rest to the old first.
header.start = rest
reverse(header)
first.next.next = first

//Set the old first to null, as it is now the last node in the list.
first.next = null

//Point the header H to the new first node.
H.next = rest

}

这被简化为不使用指针，如果您可以在伪代码中使用指针，则可以将指向“其余”节点的指针传递给后续的每个递归层。

Answer 2

此代码定义了一个单链表，其中每个节点包含数据和对下一个节点的引用。 add_to_end方法创建一个新节点并将其附加到列表的末尾，首先检查列表是否为空，然后遍历列表找到最后一个节点，最后将新节点链接到最后一个节点。这允许将新元素按顺序添加到列表末尾。

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class SinglyLinkedList:
    def __init__(self):
        self.head = None

    def add_to_end(self, data):
        # Step 1: Create the new node
        new_node = Node(data)
        
        # Step 2: Check if the list is empty
        if not self.head:
            self.head = new_node
        else:
            # Step 3: Traverse to the last node
            current = self.head
            while current.next:
                current = current.next
            
            # Step 4: Attach the new node at the end
            current.next = new_node

# Example usage:
linked_list = SinglyLinkedList()
linked_list.add_to_end(5)
linked_list.add_to_end(10)
linked_list.add_to_end(15)