【剑指 Offer】反转链表的两种解法

【剑指 Offer】反转链表的两种解法

引用

CSDN

1.

https://m.blog.csdn.net/m0_67660672/article/details/141144059

链表是计算机科学中常用的一种数据结构，而反转链表则是链表操作中的一个经典问题。本文将详细介绍两种常见的链表反转方法：三指针法和头插法，并通过具体的代码实现帮助读者理解这两种方法的原理和应用。

问题描述

给定一个单链表的头结点 pHead（该头节点是有值的，比如在下图，它的 val 是 1），长度为 n，反转该链表后，返回新链表的表头。

解题思路

反转链表有多种解法，这里介绍两种常见的方法：

1. 定义三个指针，整体右移，边移动边翻转，保证不会断链。
2. 采用头插思想进行翻转。

方法一：三指针法

这种方法通过三个指针 first、second 和 third 来实现链表的反转。具体步骤如下：

1. 初始化三个指针分别指向链表的第一个、第二个和第三个节点。
2. 在循环中，将 second 指针指向的节点的 next 指针指向 first，实现局部反转。
3. 然后将三个指针整体后移一位。
4. 当 third 指针为 null 时，说明已经到达链表尾部，此时需要处理最后两个节点的反转关系，并将原链表头节点的 next 指针置为 null。

以下是具体的代码实现：

public class Solution {
    public ListNode ReverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 不带头结点，至少有2个节点
        ListNode first = head; // 指向第一个节点
        ListNode second = first.next; // 指向第二个节点
        ListNode third = second.next; // 指向第三个节点，可能为null
        while (third != null) {
            // 翻转
            second.next = first;
            // 指针整体后移
            first = second;
            second = third;
            third = third.next;
        }
        second.next = first; // 当传入的链表只有两个节点 or 上述翻转结束时，最后一个节点并未翻转
        head.next = null; // 曾经的第一个节点，next并不是null，设置一下
        head = second; // 头指针指向最后一个节点
        return head;
    }
}

方法二：头插法

这种方法通过一个新链表 new_head 来实现链表的反转。具体步骤如下：

1. 初始化一个空的新链表头节点 new_head。
2. 在循环中，每次从原链表中取出第一个节点，并将其插入到新链表的头部。
3. 重复上述过程，直到原链表为空。

以下是具体的代码实现：

public class Solution {
    public ListNode ReverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode new_head = null;
        while (head != null) {
            // 先从原链表中去掉第一个节点
            ListNode p = head;
            head = head.next;
            // 再将p标识的节点头查到新链表
            p.next = new_head;
            new_head = p;
        }
        head = new_head;
        return head;
    }
}

这两种方法各有优劣，三指针法在空间复杂度上更优，而头插法则更简洁易懂。读者可以根据具体需求选择合适的方法。