【数据结构-链表-01】反转链表

💝💝💝欢迎来到我的博客，很高兴能够在这里和您见面！希望您在这里可以感受到一份轻松愉快的氛围，不仅可以获得有趣的内容和知识，也可以畅所欲言、分享您的想法和见解。

• 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老
• 导航
  • 檀越剑指大厂系列:全面总结 java 核心技术点,如集合,jvm,并发编程 redis,kafka,Spring,微服务,Netty 等
  • 常用开发工具系列:罗列常用的开发工具,如 IDEA,Mac,Alfred,electerm,Git,typora,apifox 等
  • 数据库系列:详细总结了常用数据库 mysql 技术点,以及工作中遇到的 mysql 问题等
  • 懒人运维系列:总结好用的命令,解放双手不香吗?能用一个命令完成绝不用两个操作
  • 数据结构与算法系列:总结数据结构和算法,不同类型针对性训练,提升编程思维,剑指大厂

非常期待和您一起在这个小小的网络世界里共同探索、学习和成长。💝💝💝 ✨✨ 欢迎订阅本专栏 ✨✨

反转链表-力扣 206 题

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

输入：head = [1,2,3,4,5]输出：[5,4,3,2,1]输入：[1,2]输出：[2,1]输入：[]输出：[]

1.解法一

题解:

class Solution:    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:        """        反转链表:定义前节点和当前节点        :param head:        :return:        """        pre, curr = None, head        while curr is not None:            next = curr.next            curr.next = pre            pre = curr            curr = next        return pre

2.解法二

构造一个新链表，从旧链表依次拿到每个节点，创建新节点添加至新链表头部，完成后新链表即是倒序的

评价：简单直白，就是得新创建节点对象

// 创建新节点public ListNode reverseList(ListNode o1) {    //创建新的链表空节点    ListNode n1 = null;    //设置临时节点,把o1指向p    ListNode p = o1;    while (p != null) {        //创建节点,新节点的下一个节点是新链表,并重置新链表的头部        n1 = new ListNode(p.val, n1);        //移动旧链表的位置        p = p.next;    }    //因为重置了n1,直接返回n1    return n1;}

3.解法三

与方法 2 类似，构造一个新链表，从旧链表头部移除节点，添加到新链表头部，完成后新链表即是倒序的，区别在于原题目未提供节点外层的容器类，这里提供一个，另外一个区别是并不去构造新节点

评价：更加面向对象，如果实际写代码而非刷题，更多会这么做

// 设计一个Listpublic ListNode reverseList(ListNode head) {    //旧链表    List o1 = new List(head);    //新链表    List n1 = new List(null);    while (true) {        //不断取旧链表的第一个元素        final ListNode listNode = o1.removeFirst();        //如果旧链表为空，则跳出循环        if (listNode == null) {            break;        }        //将旧链表的第一个元素添加到新链表的头部        n1.addFirst(listNode);    }    return n1.head;}static class List {    ListNode head;    public List(ListNode head) {        this.head = head;    }        public void addFirst(ListNode first) {        //头节点的下一个节点是head        first.next = head;        //重置head        head = first;    }        public ListNode removeFirst() {        //此时的head是旧链表的head,需要截断头节点,并返回完整的节点        ListNode first = head;        if (first != null) {            head = first.next;        }        return first;    }}

4.解法四

递归，在递归时让 $5\to 4$，$4\to 3$ …

首先，写一个递归方法，返回值用来拿到最后一个节点

• 注意 1：递归终止条件是 curr.next == null，目的是到最后一个节点就结束递归，与之前递归遍历不一样
• 注意 2：需要考虑空链表即 p == null 的情况

下面为伪码调用过程，假设节点分别是 $1\to 2\to 3\to 4\to 5\to null$，先忽略返回值

reverseList(ListNode p = 1) {    reverseList(ListNode p = 2) {    reverseList(ListNode p = 3) {    reverseList(ListNode p = 4) {    reverseList(ListNode p = 5) {    if (p == null || p.next == null) {                        return p; // 返回5                    }}                // 此时p是4, p.next是5}            // 此时p是3, p.next是4}        // 此时p是2, p.next是3}    // 此时p是1, p.next是2}

接下来，从 p = 4 开始，要让 $5\to 4$，$4\to 3$ …

reverseList(ListNode p = 1) {    reverseList(ListNode p = 2) {    reverseList(ListNode p = 3) {    reverseList(ListNode p = 4) {    reverseList(ListNode p = 5) {    if (p == null || p.next == null) {                        return p; // 返回5                    }}                // 此时p是4, p.next是5, 要让5指向4,代码写成 p.next.next=p                // 还要注意4要指向 null, 否则就死链了}            // 此时p是3, p.next是4}        // 此时p是2, p.next是3}    // 此时p是1, p.next是2}

最终解法

//递归public ListNode reverseList(ListNode p) {    if (p == null || p.next == null) {        return p; // 最后节点    }    ListNode last = reverseList(p.next);    //这里最后一个节点是倒数第二个节点    p.next.next = p;    //防止死循环,环形链表    p.next = null;    return last;}

5.解法五

从链表每次拿到第二个节点，将其从链表断开，插入头部，直至它为 null 结束

1. 设置指针 o1(旧头)、n1(新头)、o2(旧老二)，分别指向第一，第一，第二节点

$\frac{n1o1}{1}\to \frac{o2}{2}\to 3\to 4\to 5\to null$

2. 将 o2 节点从链表断开，即 o1 节点指向第三节点

$ \frac{n1 \ o1}{1} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null$ ，$\frac{o2}{2}$

3. o2 节点链入链表头部，即

$\frac{o2}{2}\to \frac{n1o1}{1}\to 3\to 4\to 5\to null$

4. n1 指向 o2

$\frac{n1o2}{2}\to \frac{o1}{1}\to 3\to 4\to 5\to null$

5. o2 指向 o1 的下一个节点，即

$\frac{n1}{2}\to \frac{o1}{1}\to \frac{o2}{3}\to 4\to 5\to null$

6. 重复以上 $2\sim 5$ 步，直到 o2 指向 null

7. 还应当考虑边界条件，即链表中不满两个元素时，无需走以上逻辑

public ListNode reverseList(ListNode o1) {    // 1. 空链表  2. 一个元素    if (o1 == null || o1.next == null) {        return o1;    }    ListNode o2 = o1.next;    //新链表的指针    ListNode n1 = o1;    while (o2 != null) {        //旧链表移动一位        o1.next = o2.next;        //取出的数据的下一个节点指向新链表的头结点        o2.next = n1;        //重置n1        n1 = o2;        //重置o2        o2 = o1.next;    }    return n1;}

6.解法六

要点：把链表分成两部分，思路就是不断从链表 2 的头，往链表 1 的头搬移

1. n1 指向 null，代表新链表一开始没有元素，o1 指向原链表的首节点

$\frac{n1}{null}$，$\frac{o1}{1}\to 2\to 3\to 4\to 5\to null$

2. 开始循环，o2 指向原链表次节点

$\frac{n1}{null}$，$\frac{o1}{1}\to \frac{o2}{2}\to 3\to 4\to 5\to null$

3. 搬移

$\frac{o1}{1}\to \frac{n1}{null}$ ， $\frac{o2}{2}\to 3\to 4\to 5\to null$

4. 指针复位

$\frac{n1}{1}\to null$ ， $\frac{o1o2}{2}\to 3\to 4\to 5\to null$

5. 重复 $2\sim 4$ 步
6. 当 o1 = null 时退出循环

//不断把 o1 头插到 n1public ListNode reverseList(ListNode o1) {    if (o1 == null || o1.next == null) {        return o1;    }    //创建空链表    ListNode n1 = null;    while (o1 != null) {        ListNode o2 = o1.next;        //取出节点后指向新节点        o1.next = n1;        //重置n1        n1 = o1;        //重置o1        o1 = o2;    }    return n1;}

觉得有用的话点个赞 👍🏻 呗。
❤️❤️❤️本人水平有限，如有纰漏，欢迎各位大佬评论批评指正！😄😄😄

💘💘💘如果觉得这篇文对你有帮助的话，也请给个点赞、收藏下吧，非常感谢!👍 👍 👍

🔥🔥🔥Stay Hungry Stay Foolish 道阻且长,行则将至,让我们一起加油吧！🌙🌙🌙

来源地址：https://blog.csdn.net/qyj19920704/article/details/132581371