反转链表：算法与实现

反转链表是一种常见的算法问题，它要求我们改变链表中元素的顺序，使得原本的顺序变为相反的顺序。例如，给定链表1->2->3->4，反转后应为4->3->2->1。

解决这个问题的一种常见方法是迭代法。首先，我们需要找到链表的头节点，然后依次迭代每一个节点，将其指向前一个节点，从而实现反转。下面是一个Python的示例代码：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
def reverseList(head: ListNode) -> ListNode:
    prev = None
    cur = head
    while cur:
        next_node = cur.next  # 保存当前节点的下一个节点
        cur.next = prev  # 将当前节点指向前一个节点
        prev = cur  # 更新prev指针指向当前节点
        cur = next_node  # 移动到下一个节点
    return prev  # 返回反转后的头节点

在这个代码中，我们首先定义了一个链表节点类ListNode，每个节点包含一个值val和一个指向下一个节点的指针next。然后，我们定义了reverseList函数，它接受一个链表头节点作为输入，并返回反转后的链表头节点。

在函数内部，我们使用三个指针：prev、cur和next_node。prev指针用于保存前一个节点，cur指针用于遍历链表，next_node指针用于保存当前节点的下一个节点。在每一次迭代中，我们首先保存当前节点的下一个节点，然后将当前节点指向前一个节点，更新prev和cur指针的位置，最后移动到下一个节点。当遍历完整个链表后，prev指针就指向了反转后的头节点，我们将其返回即可。

这个算法的时间复杂度是O(n)，空间复杂度是O(1)。因为我们只使用了常数个额外的空间，并且在遍历链表的过程中没有进行任何重复的操作。在实际应用中，我们可以使用这个算法来解决各种链表相关的问题。例如，如果我们需要在两个链表的中间节点处将它们连接起来，可以先将两个链表反转，然后在反转后的链表中查找中间节点，最后将两个链表连接起来。