怎么使用Java实现单链表的反转

# 怎么使用Java实现单链表的反转

## 目录
1. [单链表基础概念](#单链表基础概念)
2. [反转链表的算法思路](#反转链表的算法思路)
3. [迭代法实现](#迭代法实现)
4. [递归法实现](#递归法实现)
5. [栈辅助实现](#栈辅助实现)
6. [复杂度分析与对比](#复杂度分析与对比)
7. [完整代码示例](#完整代码示例)
8. [应用场景与扩展](#应用场景与扩展)

---

## 单链表基础概念
单链表（Singly Linked List）是由节点组成的线性数据结构，每个节点包含：
- **数据域**：存储实际数据
- **指针域**：指向下一个节点的地址

```java
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

特点： - 非连续内存存储 - 插入/删除时间复杂度O(1) - 随机访问时间复杂度O(n)

反转链表的算法思路

核心目标：将A->B->C->D变为D->C->B->A

关键操作步骤

1. 保存当前节点的next指针
2. 修改当前节点的next指向
3. 移动指针到下一个节点

迭代法实现

最常用且空间复杂度最优的方法（O(1)）

代码实现

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode nextTemp = curr.next; // 1.保存next节点
        curr.next = prev;              // 2.反转指针
        prev = curr;                   // 3.移动prev
        curr = nextTemp;               // 4.移动curr
    }
    return prev;
}

执行过程示例

初始状态：1 -> 2 -> 3 -> null

第1次迭代：
prev = null
curr = 1
nextTemp = 2
1.next -> null
prev = 1
curr = 2

第2次迭代：
nextTemp = 3
2.next -> 1
prev = 2
curr = 3

第3次迭代：
nextTemp = null
3.next -> 2
prev = 3
curr = null

递归法实现

更简洁但空间复杂度为O(n)（递归栈深度）

代码实现

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;      // 断开原指针
    return newHead;
}

递归调用栈分析

reverseList(1):
  reverseList(2):
    reverseList(3): return 3
  2.next.next = 2 → 3->2
  2.next = null
  return 3
1.next.next = 1 → 2->1
1.next = null
return 3

栈辅助实现

利用栈后进先出的特性实现反转

代码实现

public ListNode reverseList(ListNode head) {
    if (head == null) return null;
    Stack<ListNode> stack = new Stack<>();
    while (head != null) {
        stack.push(head);
        head = head.next;
    }
    ListNode newHead = stack.pop();
    ListNode curr = newHead;
    while (!stack.isEmpty()) {
        curr.next = stack.pop();
        curr = curr.next;
    }
    curr.next = null; // 防止循环引用
    return newHead;
}

复杂度分析与对比

完整代码示例

包含测试用例的完整实现：

public class LinkedListReverser {
    // 节点定义
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }
    }

    // 迭代法
    public static ListNode reverseIteratively(ListNode head) {
        /* 同前文实现 */
    }

    // 递归法
    public static ListNode reverseRecursively(ListNode head) {
        /* 同前文实现 */
    }

    // 打印链表
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // 构建测试链表 1->2->3->4
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);

        System.out.println("原始链表:");
        printList(head);

        System.out.println("迭代反转后:");
        printList(reverseIteratively(head));

        System.out.println("递归反转后:");
        printList(reverseRecursively(head));
    }
}

应用场景与扩展

典型应用

1. 回文链表判断
2. LRU缓存淘汰算法
3. 大数据处理中的反向遍历

变种问题

1. 反转链表前N个节点

ListNode successor = null;
ListNode reverseN(ListNode head, int n) {
    if (n == 1) {
        successor = head.next;
        return head;
    }
    ListNode newHead = reverseN(head.next, n-1);
    head.next.next = head;
    head.next = successor;
    return newHead;
}

1. 反转链表的一部分（区间反转）

ListNode reverseBetween(ListNode head, int m, int n) {
    if (m == 1) {
        return reverseN(head, n);
    }
    head.next = reverseBetween(head.next, m-1, n-1);
    return head;
}

1. K个一组反转链表

ListNode reverseKGroup(ListNode head, int k) {
    ListNode curr = head;
    int count = 0;
    while (curr != null && count < k) {
        curr = curr.next;
        count++;
    }
    if (count == k) {
        curr = reverseKGroup(curr, k);
        while (count-- > 0) {
            ListNode temp = head.next;
            head.next = curr;
            curr = head;
            head = temp;
        }
        head = curr;
    }
    return head;
}

性能优化建议

1. 对于超长链表，优先使用迭代法避免栈溢出
2. 多线程环境下考虑加锁或使用不可变链表
3. 可结合尾指针优化反转操作

注意：在实际面试中，面试官可能会要求同时写出迭代和递归两种解法，并分析它们的优缺点。建议掌握至少两种实现方式。 “`