反转链表 | java实现

moonstar

一、题目描述

给你单链表的头节点 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
————————————————
版权声明：本文为CSDN博主「爱思考的实践者」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/chinawangfei/article/details/125232032