反转链表

题目要求
解题思路
Golang 版本
C++版本
Python 版本
Java 版本
Rust 版本
总结

题目要求

你需要编写一个函数，该函数接收一个单链表的头节点 head 作为参数。你的任务是反转这个单链表，即改变链表中元素的顺序，使原本链表中的第一个元素变成最后一个元素，第二个元素变成倒数第二个元素，以此类推。最终，你需要返回新的头节点，即原链表的最后一个节点，这样我们就可以通过这个新的头节点遍历整个被反转的链表。

解题思路

反转链表是链表操作中的一个经典问题，可以通过迭代或递归的方式来解决。这里我们讨论迭代的方法，因为它的空间复杂度较低（O(1)），适合面试或考试时使用。

初始化三个指针：prev、curr 和 next。其中，prev 初始化为 null，curr 初始化为头节点 head，next 用于临时存储 curr 的下一个节点。
遍历链表：当 curr 不为 null 时，循环继续。在每次循环中，首先记录 curr 的下一个节点到 next（因为后面要改变 curr 的 next 指针）。
反转指针：将 curr 的 next 指针指向 prev。这一步实际上完成了当前节点的反转。
移动指针：将 prev 和 curr 指针都向前移动一位。具体来说，prev 移动到 curr，curr 移动到 next。
循环结束：当 curr 为 null 时，意味着我们已经处理完所有的节点，此时 prev 指向的就是反转后的链表的头节点。
返回新的头节点：最后返回 prev，因为当循环结束时，curr 是 null，而 prev 此时指向的是原链表的最后一个节点，也就是反转后链表的头节点。

注意，这个过程中我们没有创建任何新的链表节点，只是改变了现有节点的指向，因此空间复杂度保持在 O(1)，时间复杂度为 O(n)，其中 n 是链表的长度。

Golang 版本

// ListNode is the definition for singly-linked list.
type ListNode struct {
    Val  int
    Next *ListNode
}

// reverseList takes the head of a singly-linked list and returns the head of the reversed list.
func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    curr := head

    for curr != nil {
        nextTemp := curr.Next // temporarily store the next node
        curr.Next = prev      // reverse the current node's pointer
        prev = curr           // move prev and curr one step forward
        curr = nextTemp
    }
    return prev // prev is the new head at the end of the loop
}

这段代码定义了一个 ListNode 结构体，用于表示链表节点。reverseList 函数接收一个链表的头节点 head，并返回反转后链表的头节点。函数内部通过一个循环，逐个改变节点的 Next 指针，最终达到反转链表的目的。

C++版本

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// Function to reverse a singly-linked list.
ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    ListNode* next = nullptr;

    while (curr != nullptr) {
        next = curr->next;  // temporarily store the next node
        curr->next = prev;  // reverse the current node's pointer
        prev = curr;        // move prev and curr one step forward
        curr = next;
    }
    return prev;  // prev is the new head at the end of the loop
}

这段代码提供了一个 C++版本的单链表反转函数。ListNode 结构体用于定义链表节点，包含一个整数值 val 和一个指向下一个节点的指针 next。reverseList 函数接收链表的头节点 head 并返回反转后的链表的头节点。函数通过一个循环来逐个改变节点的 next 指针，从而实现链表的反转。

Python 版本

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# Function to reverse a singly-linked list.
def reverseList(head: ListNode) -> ListNode:
    prev = None
    curr = head

    while curr:
        next_temp = curr.next  # temporarily store the next node
        curr.next = prev       # reverse the current node's pointer
        prev = curr            # move prev and curr one step forward
        curr = next_temp

    return prev  # prev is the new head at the end of the loop

这段代码提供了一个 Python 版本的单链表反转函数。ListNode 类用于定义链表节点，包含一个整数值 val 和一个指向下一个节点的指针 next。reverseList 函数接收链表的头节点 head 并返回反转后的链表的头节点。函数通过一个循环来逐个改变节点的 next 指针，从而实现链表的反转。

Java 版本

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

// Function to reverse a singly-linked list.
public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    ListNode next = null;

    while (curr != null) {
        next = curr.next;  // temporarily store the next node
        curr.next = prev;  // reverse the current node's pointer
        prev = curr;       // move prev and curr one step forward
        curr = next;
    }
    return prev;  // prev is the new head at the end of the loop
}

这段代码提供了一个 Java 版本的单链表反转函数。ListNode 类用于定义链表节点，包含一个整数值 val 和一个指向下一个节点的指针 next。reverseList 方法接收链表的头节点 head 并返回反转后的链表的头节点。方法通过一个循环来逐个改变节点的 next 指针，从而实现链表的反转。

Rust 版本

#![allow(unused)]
fn main() {
// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    #[inline]
    fn new(val: i32) -> Self {
        ListNode { next: None, val }
    }
}

// Function to reverse a singly-linked list.
pub fn reverse_list(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let mut prev = None;
    let mut current = head;

    while let Some(mut node) = current {
        let next = node.next.take(); // temporarily store the next node
        node.next = prev;            // reverse the current node's pointer
        prev = Some(node);           // move prev and current one step forward
        current = next;
    }

    prev // prev is the new head at the end of the loop
}
}

这段代码提供了一个 Rust 版本的单链表反转函数。ListNode 结构体用于定义链表节点，包含一个整数值 val 和一个指向下一个节点的 Option<Box<ListNode>> 类型的 next。reverse_list 函数接收链表的头节点 head（一个 Option<Box<ListNode>> 类型）并返回反转后的链表的头节点。函数通过一个循环来逐个改变节点的 next 指针，从而实现链表的反转。

总结

上面给出了使用不同编程语言实现的单链表反转算法。无论是使用 Golang、C++、Python、Java 还是 Rust，算法的核心思想都是一致的：通过迭代遍历链表，逐个改变节点的指针指向，最终实现链表的反转。这个算法的时间复杂度为 O(n)，其中 n 是链表的长度，空间复杂度为 O(1)，因为只使用了有限的额外空间。这使得这个算法在面试或实际应用中都是一个高效且常用的链表操作。

hot-100