Java怎么實現反轉鏈表

# Java怎么實現反轉鏈表

反轉鏈表是數據結構與算法中的經典問題，也是面試高頻考點。本文將介紹Java中兩種常見的反轉鏈表實現方法：**迭代法**和**遞歸法**，并提供完整代碼示例。

## 一、鏈表節點定義
首先定義鏈表節點類：
```java
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

二、迭代法實現

時間復雜度O(n)，空間復雜度O(1)

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode nextTemp = curr.next; // 臨時保存下一個節點
        curr.next = prev;  // 反轉指針方向
        prev = curr;       // prev指針后移
        curr = nextTemp;   // curr指針后移
    }
    return prev;  // 新鏈表頭節點
}

三、遞歸法實現

時間復雜度O(n)，空間復雜度O(n)（?？臻g）

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;
}

四、方法對比

五、測試示例

// 輸入: 1->2->3->4->5->NULL
// 輸出: 5->4->3->2->1->NULL
ListNode head = new ListNode(1);
head.next = new ListNode(2);
// ...構建鏈表
ListNode reversed = reverseList(head);

掌握這兩種實現方式可以幫助開發者深入理解鏈表結構和指針操作，建議同時掌握兩種寫法以應對不同場景需求。 “`