单链表反转的分析及实现 _双向链表

单链表反转的分析及实现

基本概念

单链表是一种常见的数据结构，由一系列节点组成，每个节点包含两部分：数据域和指向下一个节点的指针域，反转单链表意味着将链表中的节点顺序逆置，例如将链表1>2>3>4>5反转为5>4>3>2>1。

创建单链表

为了深入理解反转过程，首先需要创建一个单链表，通常使用一个节点类来封装数据域和指针域：

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

可以使用以下方式创建一个单链表：

ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
// ...以此类推

单链表反转方法分析

1. 迭代法（三指针法）

这种方法使用三个指针：pre（前驱节点）、cur（当前节点）和next（后续节点），核心思想是遍历链表，不断改变当前节点的指针方向，使其指向前驱节点，具体步骤如下：

初始化：pre = null,cur = head

循环直到cur为null：

next = cur.next // 暂存下一个节点

cur.next = pre // 改变当前节点的指针方向

pre = cur // 移动前驱指针

cur = next // 移动当前指针

返回新的头结点pre

代码示例：

public ListNode reverseIteratively(ListNode head) {
    ListNode pre = null, cur = head;
    while (cur != null) {
        ListNode nextTemp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = nextTemp;
    }
    return pre;
}

2. 递归法

递归法利用函数自身调用反转剩余部分的子链表，然后将当前节点连接到反转后的子链表末尾，具体步骤如下：

如果链表为空或只有一个节点，直接返回。

否则，递归调用反转除第一个节点外的子链表。

将第一个节点接到反转后的子链表的头部。

代码示例：

public ListNode reverseRecursively(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode p = reverseRecursively(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}

3. 头插法

头插法通过改变原链表的节点指向来实现反转，具体步骤如下：

从链表头开始，将每个节点依次插入到新链表的头部。

同时改变原节点的指针方向。

直到所有节点都被重新插入。

代码示例：

public ListNode reverseByHeadInsert(ListNode head) {
    ListNode newHead = new ListNode(0);
    ListNode p = head;
    while (p != null) {
        ListNode nextTemp = p.next;
        p.next = newHead.next;
        newHead.next = p;
        p = nextTemp;
    }
    return newHead.next;
}

性能分析

时间复杂度：以上三种方法的时间复杂度均为O(N)，其中N为链表长度。

空间复杂度：迭代法的空间复杂度为O(1)；递归法的空间复杂度取决于递归深度，最坏情况下为O(N)；头插法的空间复杂度也为O(1)（不考虑新建节点带来的额外空间）。

相关问答FAQs

问1：为什么需要反转单链表？

答：在实际应用中，反转单链表可以用于多种场景，如回文检测、数据流逆序处理等，掌握链表反转技巧有助于加深对链表操作的理解，提高数据结构处理能力。

问2：如何判断一个单链表是否是回文？

答：一种方法是先将链表反转，然后逐个比较原链表和反转后链表的节点值，如果完全相同，则该链表是回文结构，另一种更高效的方法是使用双指针技术，快慢指针定位到链表中央，反转后半部分链表，再逐一比较前后半部分是否对称。

下面是一个介绍，对比了单链表和双向链表在反转操作的分析和实现上的不同：

这个介绍总结了单链表和双向链表在反转操作上的主要区别和实现步骤，由于双向链表的节点包含了指向前一个节点的指针，因此在执行反转操作时更加直观和简单，而单链表由于缺乏指向前一个节点的直接引用，需要额外的变量来保存前一个节点，以避免在反转过程中丢失链表的连接。