Hello，大家好，我是阿月。堅(jiān)持刷題，老年癡呆追不上我，今天繼續(xù)鏈表：反轉(zhuǎn)鏈表

題目

LCR 024. 反轉(zhuǎn)鏈表

思考

翻轉(zhuǎn)鏈表是一個(gè)常見的算法問(wèn)題，通常用于練習(xí)基本的數(shù)據(jù)結(jié)構(gòu)操作

實(shí)現(xiàn)

在 Java 中可以通過(guò)迭代和遞歸兩種方式來(lái)實(shí)現(xiàn)鏈表的翻轉(zhuǎn)

1. 迭代方式實(shí)現(xiàn)鏈表翻轉(zhuǎn)

• 使用三個(gè)指針prev、curr和nextTemp來(lái)逐步翻轉(zhuǎn)鏈表。
  • prev初始化為null，表示新鏈表的末尾。
  • curr從頭節(jié)點(diǎn)開始，逐步遍歷整個(gè)鏈表。
  • 在遍歷過(guò)程中，將當(dāng)前節(jié)點(diǎn)的next指向前一個(gè)節(jié)點(diǎn)，并移動(dòng)prev和curr到下一個(gè)節(jié)點(diǎn)。

class ListNode {int val;ListNode next;ListNode(int x) { val = x; }
}public class ReverseLinkedList {public static ListNode reverseList(ListNode head) {ListNode prev = null;ListNode curr = head;while (curr != null) {ListNode nextTemp = curr.next; // 保存下一個(gè)節(jié)點(diǎn)curr.next = prev; // 當(dāng)前節(jié)點(diǎn)的next指向前一個(gè)節(jié)點(diǎn)prev = curr; // 前一個(gè)節(jié)點(diǎn)移動(dòng)到當(dāng)前節(jié)點(diǎn)curr = nextTemp; // 當(dāng)前節(jié)點(diǎn)移動(dòng)到下一個(gè)節(jié)點(diǎn)}return prev; // 返回新的頭節(jié)點(diǎn)}public static void main(String[] args) {// 構(gòu)建測(cè)試鏈表：1 -> 2 -> 3 -> 4 -> 5ListNode head = new ListNode(1);head.next = new ListNode(2);head.next.next = new ListNode(3);head.next.next.next = new ListNode(4);head.next.next.next.next = new ListNode(5);// 翻轉(zhuǎn)鏈表ListNode reversedHead = reverseList(head);// 打印翻轉(zhuǎn)后的鏈表ListNode current = reversedHead;while (current != null) {System.out.print(current.val + " ");current = current.next;}}
}

2. 遞歸方式實(shí)現(xiàn)鏈表翻轉(zhuǎn)

• 遞歸地處理鏈表的剩余部分，直到到達(dá)最后一個(gè)節(jié)點(diǎn)。
• 在回溯過(guò)程中，翻轉(zhuǎn)當(dāng)前節(jié)點(diǎn)和其前一個(gè)節(jié)點(diǎn)的連接。
• 最終返回新的頭節(jié)點(diǎn)。

class ListNode {int val;ListNode next;ListNode(int x) { val = x; }
}public class ReverseLinkedList {public static ListNode reverseList(ListNode head) {// 基本情況：如果鏈表為空或只有一個(gè)節(jié)點(diǎn)，直接返回頭節(jié)點(diǎn)if (head == null || head.next == null) {return head;}// 遞歸翻轉(zhuǎn)剩余的鏈表ListNode p = reverseList(head.next);// 當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指向當(dāng)前節(jié)點(diǎn)head.next.next = head;head.next = null;return p; // 返回新的頭節(jié)點(diǎn)}public static void main(String[] args) {// 構(gòu)建測(cè)試鏈表：1 -> 2 -> 3 -> 4 -> 5ListNode head = new ListNode(1);head.next = new ListNode(2);head.next.next = new ListNode(3);head.next.next.next = new ListNode(4);head.next.next.next.next = new ListNode(5);// 翻轉(zhuǎn)鏈表ListNode reversedHead = reverseList(head);// 打印翻轉(zhuǎn)后的鏈表ListNode current = reversedHead;while (current != null) {System.out.print(current.val + " ");current = current.next;}}
}

這兩種方法在不同的場(chǎng)景下都有其優(yōu)點(diǎn)和適用性。迭代方法通常更容易理解和實(shí)現(xiàn)，而遞歸方法則更具遞歸思想的優(yōu)美性。