LinkedList链表如何进行反转操作

LinkedList 链表的反转操作可以通过迭代或递归的方式实现。这里分别给出两种方法的 Java 实现。

1. 迭代方法：

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode current = head;
    ListNode next = null;
    
    while (current != null) {
        next = current.next; // 保存下一个节点
        current.next = prev; // 反转当前节点的指针
        prev = current; // 将 prev 移动到当前节点
        current = next; // 将 current 移动到下一个节点
    }
    
    return prev; // 返回新的头节点
}

2. 递归方法：

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    
    ListNode newHead = reverseList(head.next); // 递归反转剩余部分
    head.next.next = head; // 将当前节点添加到反转后的链表末尾
    head.next = null; // 将当前节点的 next 指针置为 null
    
    return newHead; // 返回新的头节点
}

这两种方法都可以实现 LinkedList 链表的反转操作。迭代方法的时间复杂度为 O(n)，空间复杂度为 O(1)；递归方法的时间复杂度为 O(n)，空间复杂度为 O(n)。在实际应用中，可以根据具体需求选择合适的方法。