链表反转算法详解

链表反转算法

1、双指针法

双指针法是一种常用的链表操作技巧，通过两个指针的配合，可以在遍历链表的过程中逐步完成链表的反转。

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* current = head;
        while (current != nullptr) {
            ListNode* nextNode = current->next;
            current->next = prev;
            prev = current;
            current = nextNode;
        }
        return prev;
    }
};

在Python中，同样的逻辑可以通过如下代码实现：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def reverseList(self, head):
        prev = None
        current = head
        while current is not None:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node
        return prev

2、递归法

递归法是另一种实现链表反转的方法，其核心思想是将问题分解为更小的子问题，直到达到基本情况，然后逐步解决每个子问题，最终完成整个链表的反转。

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        return reverse(nullptr, head);
    }
private:
    ListNode* reverse(ListNode* prev, ListNode* current) {
        if (current == nullptr) {
            return prev;
        }
        ListNode* nextNode = current->next;
        current->next = prev;
        return reverse(current, nextNode);
    }
};

同样地，Python中的递归实现如下：

class Solution:
    def reverseList(self, head):
        def reverse(prev, current):
            if current is None:
                return prev
            next_node = current.next
            current.next = prev
            return reverse(current, next_node)
        return reverse(None, head)