当前位置：首页 > news >正文

坚持刷题｜反转链表

news 来源：原创 2024/9/29 13:17:25

文章目录

题目
思考
实现
- 1. 迭代方式实现链表翻转
- 2. 递归方式实现链表翻转

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;}}
}