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

leetcode206---反转链表---java实现

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

leetcode206---反转链表---java实现

一、题目描述

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

示例 1:

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

输出:[5,4,3,2,1]

示例 2:

 输入:head = [1,2]

输出:[2,1]

示例 3:

输入:head = []

输出:[]

提示:

  • 链表中节点的数目范围是 [0, 5000]
  • -5000 <= Node.val <= 5000

进阶:链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题?

二、解法

方法一:迭代法

将当前节点的next直接指向上一个节点,上一个节点的指针值指向当前节点,当前节点的指针值指向下一个节点。直到取不到当前节点,遍历结束,将head的next指向最后一个节点。

方法二:递归法

递归反转链表,找到倒数第个二节点和倒数第一个节点,将倒数第一个节点的指针指向倒数第二个节点,逐次递归,直到第一个节点。最后,将head的next指向最后一个节点。

三、java代码实现

节点类:

public class ListNode {
    public int no;
    public ListNode next;

    public ListNode(int no) {
        this.no = no;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                '}';
    }

链表类:

public class LinkedList {
    private ListNode head; // head节点

    public LinkedList() {
        head = new ListNode(0);
        head.no = 0;
        head.next = null;
    }

    public ListNode getHead() {
        return head;
    }

    // 显示链表
    public void showNode() {
        if (head.next == null) {
            System.out.println("链表为空!");
            return;
        }

        ListNode temp = head.next;
        while (temp != null) {
            System.out.print(temp.no + " ");
            temp = temp.next;
        }
    }

    // 添加元素
    public void addNode(ListNode node) {
        ListNode temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        node.next = temp.next;
        temp.next = node;
    }

    // 迭代实现链表反转
    public void reversIterate() {
        // 链表为空或者链表只有一个节点的时候,不需要反转
        if (head.next == null || head.next.next == null) {
            System.out.println("链表无需反转!");
            return;
        }

        ListNode previewNode = null; // 前一个节点指针
        ListNode currentNode = head.next; // 当前节点指针
        ListNode nextNode; // 下一个节点指针
        while (currentNode != null) {
            nextNode = currentNode.next;  // 保存当前节点的next值
            currentNode.next = previewNode; // 当前节点的next值指向前一个节点
            previewNode = currentNode; // 前一个节点指针指向当前节点
            currentNode = nextNode; // 当前节点指针指向下一个节点
        }
        head.next = previewNode;
    }

    public void reverseRecurse() {
        head.next = reverseNodeRecurse(head.next);
    }

    // 递归实现链表反转
    public ListNode reverseNodeRecurse(ListNode currentNode) {
        if (currentNode == null || currentNode.next == null) {
            return currentNode;
        }

        // 递归当前节点的下一个节点
        ListNode nextNode = reverseNodeRecurse(currentNode.next);
        currentNode.next.next = currentNode;
        currentNode.next = null;
        return nextNode;
    }
}

 测试实现类:

public class ListNodeReverse {

    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        // 创建并添加数值节点
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(4);
        ListNode n5 = new ListNode(5);
        linkedList.addNode(n1);
        linkedList.addNode(n2);
        linkedList.addNode(n3);
        linkedList.addNode(n4);
        linkedList.addNode(n5);

        System.out.println("反转之前:");
        linkedList.showNode();
        System.out.println();

        System.out.println("迭代反转之后:");
        linkedList.reversIterate();
        linkedList.showNode();
        System.out.println();

        System.out.println("再次递归反转:");
        linkedList.reverseRecurse();
        linkedList.showNode();
    }
}

运行结果如下所示:

反转之前:
1 2 3 4 5 
迭代反转之后:
5 4 3 2 1 
再次递归反转:
1 2 3 4 5 

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

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

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