可以使用遞歸或迭代的方式來實現反轉鏈表。
遞歸方式:
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; // 返回新的頭節點
}
}
以上是兩種常見的反轉鏈表的實現方式。