您现在的位置是:首页 >学无止境 >力扣206反转链表:代码实现+图文全解+方法总结(四种方法)网站首页学无止境

力扣206反转链表:代码实现+图文全解+方法总结(四种方法)

是谢添啊 2024-06-17 06:01:02
简介力扣206反转链表:代码实现+图文全解+方法总结(四种方法)

第一部分:题目描述

? 链接:206. 反转链表 - 力扣(LeetCode)

⭐ 难度:简单

image-20230511000929405

第二部分:题解

? ListNode类

public class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

2.1 方法一:生成新节点到新链表

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

    public static ListNode reverseList(ListNode head) {
        // 1.新链表的头节点,初始为 null
        ListNode newHead = null;
        // 2.指针 tmp 用于遍历 旧链表
        ListNode tmp = head;

        // 3.进行链表遍历
        while (tmp != null) {
            // 3.1 创建一个新节点 node,存储的val值为遍历到的旧链表的节点值 
            ListNode node = new ListNode(tmp.val);
            // 3.2 指定新节点的下一个节点为当前新链表头节点
            node.next = newHead;
            // 3.3 将新节点 node 指定为新的新链表头节点
            newHead = node;
            // 3.4 继续向后遍历旧链表
            tmp = tmp.next;
        }
        // 4.返回新链表头节点
        return newHead;
    }

优化:

    public static ListNode reverseList(ListNode head) {
        // 1.新链表的头节点,初始为 null
        ListNode newHead = null;
        // 2.指针 tmp 用于遍历 旧链表
        ListNode tmp = head;

        // 3.进行链表遍历
        while (tmp != null) {
            // 3.1 创建一个新节点,并指定新节点的值为当前遍历到的旧链表节点值,下一个节点为当前新链表的头节点
            //     修改新链表的头节点为创建的新节点
            newHead = new ListNode(tmp.val, newHead);
            // 3.2 继续向后遍历旧链表
            tmp = tmp.next;
        }
        // 4.返回新链表头节点
        return newHead;
    }

评价:简单直白,就是得新创建节点对象。

2.2 方法二:复用旧节点到新链表

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

? 面向过程式思想方法

    public static ListNode reverseList(ListNode head) {
        // 1.新链表的头节点,初始为 null
        ListNode newHead = null;
        // 2.指针 tmp 用于遍历 旧链表
        ListNode tmp = head;

        // 3.进行链表遍历
        while (tmp != null) {
            // 3.1 临时存储 tmp 的下一个节点
            ListNode node = tmp.next;
            // 3.2 指定 tmp 的下一个节点为当前新链表的头节点,实际是为了拼接已存在的新链表节点
            tmp.next = newHead;
            // 3.3 设置新链表的头节点为 当前tmp指针指向的节点
            newHead = tmp;
            // 3.4 设置 tmp指针 指向临时存储的节点
            tmp = node;
        }
        // 4.返回新链表头节点
        return newHead;
    }

? 面向对象式思想方法

我们还可以使用另一种方式来表达该方法的意思:【更加面向对象,如果实际写代码而非刷题,更多会这么做】

    static class List {
        ListNode head;

        public List(ListNode head) {
            this.head = head;
        }

        /**
         * 移除第一个节点
         *
         * @return 被移除的节点
         */
        public ListNode removeFirst() {
            // 1.获取原链表的第一个节点
            ListNode first = head;
            // 2.如果存在节点,则将被删除的节点的下一个节点设置为新的头节点
            if (first != null) {
                head = first.next;
            }
            // 3.返回被删除的节点
            return first;
        }

        /**
         * 添加节点到第一个元素的位置(作为头节点)
         *
         * @param first 需要添加作为新头节点的节点
         */
        public void addFirst(ListNode first) {
            // 1.设置新头节点的下一个节点为原头节点,目的是进行链表节点拼接
            first.next = head;
            // 2.设置新节点为新头节点
            head = first;
        }
    }

    public static ListNode reverseList(ListNode head) {
        // 1.设置 旧链表
        List oldList = new List(head);
        // 2.设置 新链表
        List newList = new List(null);

        // tmp指针用于遍历
        ListNode tmp = null;
        // 3.移除旧链表的当前头节点 node,赋给 tmp。
        // 如果不为空说明移除成功,如果为空说明已经全部遍历完旧链表,旧链表已无节点
        while ((tmp = oldList.removeFirst()) != null) {
            // 4.将从旧链表移除的头节点 node 添加到新链表的头部作为新的头节点
            newList.addFirst(tmp);
        }
        // 5.返回新链表的头节点
        return newList.head;
    }

2.3 方法三:递归

下面为伪码调用过程,假设节点分别是 1 → 2 → 3 → 4 → 5 → n u l l 1 ightarrow 2 ightarrow 3 ightarrow 4 ightarrow 5 ightarrow null 12345null,先忽略返回值。

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 → 4 5 ightarrow 4 54 4 → 3 4 ightarrow 3 43

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 static ListNode reverseList(ListNode head) {
        /*
            以 旧链表为 1 -> 2 -> 3 为例
         */

        /*
            递归终止条件是 curr.next == null,目的是到最后一个节点就结束递归
            需要考虑空链表即 p == null 的情况
         */
        if (head == null || head.next == null) {
            return head; // 最后一个节点
        }

        // 比如此时的 head.val 为 2

        // 拿到最后一个节点为3
        ListNode last = reverseList(head.next);
        // 节点3 的下一个节点指向 节点2
        head.next.next = head;
        /*
            节点2 的下一个节点不再指向 节点3
            为什么要加这句话?
            主要是当递归回到 head.val 为1 的时候,如果不加这句话,则会导致 节点1 和 节点2 存在相互指向的问题,
            而导致了在遍历新链表的时候会在 节点1 和 节点2 之间不断循环
         */
        head.next = null;

        // 每次递归方法返回的都是同样的值 —— 最后一个节点
        return last;
    }

Q:为啥不能在的过程中倒序?

A:比如

  • $ 1 ightarrow 2 ightarrow 3 $ 如果递的过程中让 2 → 1 2 ightarrow 1 21 那么此时 2 → 3 2 ightarrow 3 23 就被覆盖,不知道接下来递给谁
  • 而归的时候让 3 → 2 3 ightarrow 2 32 不会影响上一层的 1 → 2 1 ightarrow 2 12

评价:单向链表没有 prev 指针,但利用递归的特性 记住了 链表每次调用时相邻两个节点是谁

2.4 旧链表中移动旧节点

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

image-20230511021447365

image-20230511021521799

image-20230511021549739

    public static ListNode reverseList(ListNode head) {

        if (head == null || head.next == null) {
            return head;
        }

        // 1.设置新链表 newHead 初始指向 旧链表的头节点
        ListNode newHead = head;
        // 2.设置旧链表的头节点,由于 oldHead 不会更改,其实可以直接使用 head,但为了方便理解,还是单独使用一个指针 oldHead0
        ListNode oldHead = head;

        // 用于指向当前需要移动的节点
        ListNode tmp;

        // 3.节点移动

        // 3.1 获取旧链表头节点的下一个节点,直到旧链表只剩下了一个节点即只有旧头节点
        while ((tmp = oldHead.next) != null) {
            // 3.2 将 tmp 从旧链表中移除
            oldHead.next = tmp.next;
            // 3.3 将 tmp 移动到新链表头节点的前面
            tmp.next = newHead;
            // 3.4 将 tmp 设置为新链表新的头节点
            newHead = tmp;
        }

        // 4.返回新链表新的头节点
        return newHead;
    }
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。