数据结构单链表的逆置代码

数据结构中的单链表逆置通常涉及两个步骤：首先创建一个新的头节点，然后遍历原链表，将当前节点指向下一个是新的头部，并更新新头部的位置。以下是Python的一个简单实现：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseList(head):
    prev = None
    current = head
    while current is not None:
        # 保存当前节点的下一个节点
        next_node = current.next
        # 将当前节点指向prev
        current.next = prev
        # 更新prev和current
        prev = current
        current = next_node
    # 新链表的头就是原来的尾部
    return prev

在这个函数中，`prev` 和 `current` 分别表示上一个节点和当前节点，当 `current` 为空时，说明已经遍历完原链表，`prev` 就是新的头节点。

相关问题

java数据结构之单链表逆置代码

在Java中，单链表逆置的一个常见方法是使用迭代的方式，通过三个指针分别指向当前节点、前一个节点和下一个节点，然后逐步更新它们的位置。以下是基本的代码示例：

public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

public ListNode reverseList(ListNode head) {
    ListNode prev = null; // 初始化前驱节点为null
    ListNode curr = head; // 当前节点初始化为头节点

    // 只要当前节点不为空就继续遍历
    while (curr != null) {
        ListNode nextTemp = curr.next; // 保存当前节点的下一个节点
        curr.next = prev; // 将当前节点的next指向前一个节点
        prev = curr; // 移动前驱节点到当前节点
        curr = nextTemp; // 移动当前节点到下一个节点
    }

    return prev; // 返回新的头节点，即原链表的尾部
}

这段代码首先创建两个临时变量`prev`和`curr`，然后在循环中不断更新这两个指针，同时将`curr.next`指向`prev`，直到`curr`变为`null`。最后返回`prev`，它指向的就是原链表的反转后的头部。

示例数据结构：编写函数实现单链表逆置代码

在编程中，反转单链表是一个常见的操作，可以使用迭代或递归的方式实现。这里提供一个使用迭代法的Python示例代码：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseList(head):
    prev = None  # 初始化前驱节点为None
    current = head  # 当前节点初始化为头节点

    while current is not None:  # 当当前节点非空
        next_temp = current.next  # 记录下一个节点
        current.next = prev  # 将当前节点的next指向前驱节点
        prev = current  # 移动前驱节点到当前位置
        current = next_temp  # 移动当前节点到下一个节点

    return prev  # 返回新的头节点，即原链表的尾部

# 使用示例
# 创建链表：1 -> 2 -> 3 -> 4 -> 5
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)

# 反转链表
reversed_head = reverseList(head)

# 打印逆置后的链表：5 -> 4 -> 3 -> 2 -> 1
while reversed_head:
    print(reversed_head.val, end=" -> ")
    reversed_head = reversed_head.next

在这个例子中，`reverseList`函数接收一个链表的头节点作为输入，通过循环和临时变量交换节点，实现了链表的逆置。