java如何實現反轉列表

155次閱讀

共計 836 個字符，預計需要花費 3 分鐘才能閱讀完成。

可以使用遞歸或迭代的方式來實現反轉鏈表。

遞歸方式：

class ListNode {int val;
    ListNode next;
    ListNode(int val) {this.val = val;
    }
}

public class Solution {public ListNode reverseList(ListNode head) {// 如果鏈表為空或只有一個節點，無需反轉，直接返回原鏈表頭節點 
        if (head == null || head.next == null) {return head;
        }
        
        ListNode newHead = reverseList(head.next); // 反轉以 head.next 為頭節點的子鏈表 
        head.next.next = head; // 將 head 節點連接到反轉后的子鏈表的尾部 
        head.next = null; // 將 head 節點的 next 置為 null
        
        return newHead; // 返回新的頭節點 
    }
}

迭代方式：

class ListNode {int val;
    ListNode next;
    ListNode(int val) {this.val = val;
    }
}

public class Solution {public ListNode reverseList(ListNode head) {// 如果鏈表為空或只有一個節點，無需反轉，直接返回原鏈表頭節點 
        if (head == null || head.next == null) {return head;
        }
        
        ListNode prev = null; // 當前節點的前一個節點 
        ListNode curr = head; // 當前節點 
        
        while (curr != null) {ListNode next = curr.next; // 當前節點的下一個節點 
            curr.next = prev; // 反轉指針指向前一個節點 
            prev = curr; // 更新當前節點的前一個節點 
            curr = next; // 更新當前節點為下一個節點 
        }
        
        return prev; // 返回新的頭節點 
    }
}