在Java中實現單鏈表的逆序,可以通過迭代或遞歸兩種方式。以下是兩種方法的詳細實現:
1. 迭代方法(推薦)
public class ListNode {int val;ListNode next;ListNode(int x) { val = x; }
}class Solution {public ListNode reverseList(ListNode head) {ListNode prev = null;ListNode curr = head;while (curr != null) {ListNode nextTemp = curr.next; // 保存下一個節點curr.next = prev; // 反轉指針prev = curr; // 移動prevcurr = nextTemp; // 移動curr}return prev; // prev現在是新的頭節點}
}
2. 遞歸方法
class Solution {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;}
}