栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

【链表反转】介绍几种常见的链表反转方法(递归、迭代、穿针引线法)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

【链表反转】介绍几种常见的链表反转方法(递归、迭代、穿针引线法)

【链表反转】介绍几种常见的链表反转方法(递归、迭代、穿针引线法)。

目录

一、链表操作定义

1.1、链表结构定义

1.2、链表工具类

二、反转整个链表

2.1、常规方法

(1)【头插法】具体代码实现

(2)【头插法】画图解析

(3)【头插法】优化

2.2、递归方法

(1)【递归】代码实现

(2)【递归】画图解析

2.3、迭代方法

(1)【迭代】代码实现

(2)【迭代】画图解析

三、反转部分链表

3.1、拼接三段链表

3.2、【头插法】穿针引线法


一、链表操作定义

1.1、链表结构定义
public class ListNode {
    public int val;
    public ListNode next;
    public ListNode() {};
    public ListNode(int val) {
        this.val = val;
    };
    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    };
}

1.2、链表工具类
public class ListNodeUtil {
    
    public static ListNode getHead(int[] nums) {
        // 定义哑节点
        ListNode dummy = new ListNode(-1);
        ListNode head = dummy;
        for (int i = 0; i < nums.length; i++) {
            head.next = new ListNode(nums[i]);
            head = head.next;
        }
        // 返回头结点
        return dummy.next;
    }

    
    public static void printListNode(ListNode head) {
        ListNode temp = head;
        while (temp != null) {
            System.out.print(temp.val);
            if (temp.next != null) {
                System.out.print("-->");
            }
            temp = temp.next;
        }
        System.out.println();
    }
}

二、反转整个链表

2.1、常规方法

问题描述:

  • 有一个链表,【1-->2-->3-->4-->5】,要求将其反转成为【5-->4-->3-->2-->1】的结果。

第一种想到的链表反转方法,就是遍历链表,然后采用【头插法】来创建一个新的链,这样子就把原先链表进行了反转。

(1)【头插法】具体代码实现
public class HeadInsertion {

    
    public static ListNode reverseListNode(ListNode head) {
        // 创建一个新链表
        ListNode dummy = new ListNode(-1);
        ListNode temp = head;
        while (temp != null) {
            // 【头插法】: 每次将新的结点直接插入头结点后面
            ListNode node = new ListNode(temp.val);
            node.next = dummy.next;
            dummy.next = node;
            // 遍历下一个链表结点
            temp = temp.next;
        }
        // 返回反转后的结点
        return dummy.next;
    }

    public static void main(String[] args) {
        int[] nums = {1,2,3,4,5};
        System.out.println("--------- 原先链表 ----------");
        ListNode head = ListNodeUtil.getHead(nums);
        ListNodeUtil.printListNode(head);

        System.out.println("--------- 反转链表 ----------");
        ListNode reverseHead = reverseListNode(head);
        ListNodeUtil.printListNode(reverseHead);
    }
}

反转后的结果如下所示:

(2)【头插法】画图解析

【头插法】操作链表的核心代码:

// 【头插法】: 每次将新的结点直接插入头结点后面
// node: 表示当前待插入的结点
ListNode node = new ListNode(temp.val);
// 首先将 node 下一个结点指向 head 头结点下一个结点
node.next = head.next;
// 将 head 头结点下一个结点指向 node 结点
head.next = node;

【头插法】大致原理图如下所示:

(3)【头插法】优化

前面的【头插法】每次都会创建一个新的【ListNode】结点,这显然有点浪费内存空间了,我们其实可以直接利用原先链表的结点,从而避免创建新结点。

public static ListNode reverseListNode(ListNode head) {
    // 创建一个新链表
    ListNode dummy = new ListNode(-1);
    ListNode temp = head;
    while (temp != null) {
        // 保存当前 temp 结点
        ListNode node = temp;
        // temp 结点移动到下一个链表结点
        temp = temp.next;
        // 【头插法】: 每次将新的结点直接插入头结点后面
        node.next = dummy.next;
        dummy.next = node;
    }
    // 返回反转后的结点
    return dummy.next;
}

这种利用原先结点的方式,需要定义一个变量保存原先链表结点,然后将temp结点移动到下一个结点,之后才可以进行【头插法】操作。

2.2、递归方法

问题描述:

  • 有一个链表,【1-->2-->3-->4-->5】,要求将其反转成为【5-->4-->3-->2-->1】的结果。

(1)【递归】代码实现
public class RecursionReverse {
    
    public static ListNode reverseListNode(ListNode head) {
        // 递归终止条件: 当前结点、下一个结点为 null 时候, 递归结束
        if (head == null || head.next == null) {
            return head;
        }
        // 递归逻辑: 继续下一个结点的递归
        ListNode newHead = reverseListNode(head.next);
        // 递归结束后: 逆转两个结点的顺序
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    public static void main(String[] args) {
        int[] nums = {1,2,3,4,5};
        System.out.println("--------- 原先链表 ----------");
        ListNode head = ListNodeUtil.getHead(nums);
        ListNodeUtil.printListNode(head);

        System.out.println("--------- 反转链表 ----------");
        ListNode reverseHead = reverseListNode(head);
        ListNodeUtil.printListNode(reverseHead);
    }

}

(2)【递归】画图解析

 

 递归的方式,比较难以理解,并且递归需要额外的空间复杂度【O(n)】,这和递归的次数有关。

2.3、迭代方法

问题描述:

  • 有一个链表,【1-->2-->3-->4-->5】,要求将其反转成为【5-->4-->3-->2-->1】的结果。

(1)【迭代】代码实现
public class IterationReverse {
    
    public static ListNode reverseListNode(ListNode head) {
        // 当前结点
        ListNode curr = head;
        // 保存当前节点的前一个结点
        ListNode newHead = null;
        // 【迭代】开始遍历链表
        while (curr != null) {
            // 保存下一个结点
            ListNode next = curr.next;
            // 当前结点的下一个结点指向前一个结点位置
            curr.next = newHead;
            // 前一个结点指向当前结点
            newHead = curr;
            // 当前结点移动到下一个结点
            curr = next;
        }
        // 返回头结点
        return newHead;
    }

    public static void main(String[] args) {
        int[] nums = {1,2,3,4,5};
        System.out.println("--------- 原先链表 ----------");
        ListNode head = ListNodeUtil.getHead(nums);
        ListNodeUtil.printListNode(head);

        System.out.println("--------- 反转链表 ----------");
        ListNode reverseHead = reverseListNode(head);
        ListNodeUtil.printListNode(reverseHead);
    }
}

(2)【迭代】画图解析

 

 依次类推,迭代完成之后,整个链表就被反转了。

三、反转部分链表

3.1、拼接三段链表

问题描述:

  • 有一个链表,【1-->2-->3-->4-->5】,要求反转链表中的部分结点。
  • 例如:反转链表中第2个到第4个结点,使其成为【1-->4-->3-->2-->5】的结果。

解决思路:

  • 找到第一段链表。
  • 找到需要反转的那一段链表,然后将其单独反转。
  • 找到最后一段的链表。
  • 三段链表找到之后,将其拼接成一个完整的链表。
public class ReverseNode {

    
    public static ListNode reverseListNode(ListNode head, int left, int right) {
        // 1、找到第一段链表
        ListNode ans = new ListNode(-1, head);
        ListNode pre = ans;
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        // 2、找到第二段链表
        ListNode midHead = pre.next;
        ListNode mid = midHead;
        pre.next = null; // 断开第一段链表
        for (int i = 0; i < right - left; i++) {
            mid = mid.next;
        }
        // 3、找到第三段链表
        ListNode lastHead = mid.next;
        mid.next = null; // 断开第二段链表
        // 4、反转中间链表
        ListNode newHead = reverse(midHead);
        ListNode temp = newHead;
        while (temp != null && temp.next != null) {
            temp = temp.next;
        }
        // 5、拼接链表
        pre.next = newHead;
        temp.next = lastHead;
        return ans.next;
    }
    
    public static ListNode reverse(ListNode head) {
        ListNode newHead = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = newHead;
            newHead = curr;
            curr = next;
        }
        return newHead;
    }

    public static void main(String[] args) {
        int[] nums = {1,2,3,4,5};
        System.out.println("--------- 原先链表 ----------");
        ListNode head = ListNodeUtil.getHead(nums);
        ListNodeUtil.printListNode(head);

        System.out.println("--------- 反转链表 ----------");
        ListNode reverseHead = reverseListNode(head, 2, 4);
        ListNodeUtil.printListNode(reverseHead);
    }

}

3.2、【头插法】穿针引线法

问题描述:

  • 有一个链表,【1-->2-->3-->4-->5】,要求反转链表中的部分结点。
  • 例如:反转链表中第2个到第4个结点,使其成为【1-->4-->3-->2-->5】的结果。
public class ReverseNode2 {

    
    public static ListNode reverseListNode(ListNode head, int left, int right) {
        // 1、找到第一段链表
        ListNode ans = new ListNode(-1, head);
        ListNode pre = ans;
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        // 2、开始反转链表
        ListNode curr = pre.next;
        ListNode next = null;
        for (int i = 0; i < right - left; i++) {
            // 首先保存当前结点的下一个结点
            next = curr.next;
            // 将当前结点指向next结点的下一个结点
            curr.next = next.next;
            // 将next结点指向当前curr结点
            next.next = pre.next;
            // 将pre前一个结点指向next结点
            pre.next = next;
        }
        return ans.next;
    }

    public static void main(String[] args) {
        int[] nums = {1,2,3,4,5};
        System.out.println("--------- 原先链表 ----------");
        ListNode head = ListNodeUtil.getHead(nums);
        ListNodeUtil.printListNode(head);

        System.out.println("--------- 反转链表 ----------");
        ListNode reverseHead = reverseListNode(head, 2, 4);
        ListNodeUtil.printListNode(reverseHead);
    }

}

运行结果如下所示:

 链表的操作,关键在于需要理清楚每个结点之间如何指向,确实有一点难以理解,可以借助图形理解。


小试牛刀:

  • 206. 反转链表
  • 92. 反转链表 II

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/970445.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号