java怎么實現單鏈表反轉

184次閱讀

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

要實現單鏈表的反轉，可以使用迭代或遞歸兩種方法。

迭代法：

public ListNode reverseList(ListNode head) {ListNode prev = null; // 用于存儲反轉后的鏈表 
    ListNode curr = head; // 當前節點 
    while (curr != null) {ListNode nextTemp = curr.next; // 保存下一個節點 
        curr.next = prev; // 將當前節點的 next 指向前一個節點，實現反轉 
        prev = curr; // 將 prev 指向當前節點，為下一次迭代做準備 
        curr = nextTemp; // 將當前節點指向下一個節點，進行下一次迭代 
    }
    return prev; // 返回反轉后的鏈表的頭節點 
}

遞歸法：

public ListNode reverseList(ListNode head) {if (head == null || head.next == null) {return head; // 如果鏈表為空或只有一個節點，則直接返回 
    }
    ListNode p = reverseList(head.next); // 遞歸反轉除第一個節點以外的鏈表 
    head.next.next = head; // 將第一個節點的 next 的 next 指向第一個節點，實現反轉 
    head.next = null; // 將第一個節點的 next 指向 null，防止形成環 
    return p; // 返回反轉后的鏈表的頭節點 
}