坚持刷题｜反转链表

Hello，大家好，我是阿月。坚持刷题，老年痴呆追不上我，今天继续链表：反转链表

题目

LCR 024. 反转链表

思考

翻转链表是一个常见的算法问题，通常用于练习基本的数据结构操作

实现

在 Java 中可以通过迭代和递归两种方式来实现链表的翻转

1. 迭代方式实现链表翻转

• 使用三个指针prev、curr和nextTemp来逐步翻转链表。
  • prev初始化为null，表示新链表的末尾。
  • curr从头节点开始，逐步遍历整个链表。
  • 在遍历过程中，将当前节点的next指向前一个节点，并移动prev和curr到下一个节点。

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; // 保存下一个节点curr.next = prev; // 当前节点的next指向前一个节点prev = curr; // 前一个节点移动到当前节点curr = nextTemp; // 当前节点移动到下一个节点}return prev; // 返回新的头节点}public static void main(String[] args) {// 构建测试链表：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);// 翻转链表ListNode reversedHead = reverseList(head);// 打印翻转后的链表ListNode current = reversedHead;while (current != null) {System.out.print(current.val + " ");current = current.next;}}
}

2. 递归方式实现链表翻转

• 递归地处理链表的剩余部分，直到到达最后一个节点。
• 在回溯过程中，翻转当前节点和其前一个节点的连接。
• 最终返回新的头节点。

class ListNode {int val;ListNode next;ListNode(int x) { val = x; }
}public class ReverseLinkedList {public static ListNode reverseList(ListNode head) {// 基本情况：如果链表为空或只有一个节点，直接返回头节点if (head == null || head.next == null) {return head;}// 递归翻转剩余的链表ListNode p = reverseList(head.next);// 当前节点的下一个节点指向当前节点head.next.next = head;head.next = null;return p; // 返回新的头节点}public static void main(String[] args) {// 构建测试链表：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);// 翻转链表ListNode reversedHead = reverseList(head);// 打印翻转后的链表ListNode current = reversedHead;while (current != null) {System.out.print(current.val + " ");current = current.next;}}
}

这两种方法在不同的场景下都有其优点和适用性。迭代方法通常更容易理解和实现，而递归方法则更具递归思想的优美性。