从数组与链表到单链表的反转，一文带你吃透("深入解析：从数组与链表基础到单链表反转技巧全掌握")

原创

ithorizon 7个月前 (10-20) 阅读数 12 #后端开发

深入解析：从数组与链表基础到单链表反转技巧全掌握

一、数组与链表基础

在计算机科学中，数组和链表是两种基本的数据结构，它们在存储和访问数据方面各有特点。

1. 数组

数组是一种线性数据结构，用于存储具有相同数据类型的元素集合。数组的特点是：

在内存中占用连续的空间；

可以通过索引飞速访问元素；

大小固定，无法动态扩展。

2. 链表

链表是一种动态数据结构，由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。链表的特点是：

在内存中不占用连续的空间；

无法通过索引飞速访问元素；

大小动态可变，可以结合需要添加或删除节点。

二、单链表及其反转

单链表是链表的一种，每个节点只包含一个指向下一节点的指针。单链表的反转是指将链表的头部和尾部颠倒，让原本的尾部成为头部，头部成为尾部。

1. 单链表的反转算法

单链表反转算法的核心思想是：遍历链表，同时改变每个节点的指针方向。以下是单链表反转的步骤：

定义一个哑节点（dummy node），用于简化边界条件处理；

定义三个指针：prev、curr、next，分别即前一个节点、当前节点和下一个节点；

遍历链表，将当前节点的下一个节点赋值给next；

将当前节点的下一个节点指向prev；

将prev和curr分别向前移动一位；

当curr为null时，遍历完成，prev指向反转后的链表头部。

2. 单链表反转代码示例


class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}
public class LinkedListReversal {
    public static ListNode reverseList(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode prev = dummy;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        ListNode reversedHead = reverseList(head);
        while (reversedHead != null) {
            System.out.print(reversedHead.val + " ");
            reversedHead = reversedHead.next;
        }
    }
}