Java 算法篇-深入了解单链表的反转（实现：用 5 种方式来具体实现）

以下是实现单链表反转的 5 种方法的示例代码：

1. 递归反转

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}

2. 迭代反转

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

3. 交换节点反转

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode nextTemp = curr.next; // Temporarily store the next node
        curr.next = prev; // Reverse the link
        prev = curr; // Move forward on the list
        curr = nextTemp; // Move forward on the list
    }
    return prev;
}

4. 使用栈

public ListNode reverseList(ListNode head) {
    Deque<ListNode> stack = new LinkedList<>();
    ListNode current = head;
    while (current != null) {
        stack.push(current);
        current = current.next;
    }
    current = stack.poll();
    ListNode newHead = current;
    while (!stack.isEmpty()) {
        current.next = stack.poll();
        current = current.next;
    }
    current.next = null;
    return newHead;
}

5. 使用头插法

public ListNode reverseList(ListNode head) {
    ListNode newHead = null;
    while (head != null) {
        ListNode next = head.next; // Temporarily store the next node
        head.next = newHead; // Reverse the link
        newHead = head; // Move forward on the list
        head = next; // Move forward on the list
    }
    return newHead;
}

以上每种方法都是单链表反转的有效方式，选择合适的方法取决于特定的应用场景和性能要求。