反转链表的Java实现_反转链表java实现

目录

1、迭代法

2、递归方式

反转链表：

输入：1->2->3->4->5
输出：5->4->3->2->1

1、迭代法

思路：遍历整个链表，当链表不为空时，每次取链表的第一个Node作为当前节点，修改当前Node的指针，重复此步骤，步骤解析如下：

Java代码的具体实现步骤

    public static ListNode reverseNode_1(ListNode node) {
        ListNode previous = null, current, next;
        current = node;
        // 如果当前node不为空,遍历链表
        while (current != null) {
            // 保存当前节点的链接
            next = current.next;
            // 修改当前节点的链接,更改为指向之前的节点
            current.next = previous;
 
            // 修改之前的节点的值为当前节点
            previous = current;
            // 修改当前节点的值,继续向下遍历
            current = next;
        }
        return previous;
    }

2、递归方式

思路：使用递归，需要满足递归需要的条件

    public static ListNode reverseNode_2(ListNode node) {
        // 终止条件和终止方法
        if (node == null || node.next == null) {
            return node;
        }
        // 把node替换为node.next继续向下寻找
        ListNode new_node = reverseNode_2(node.next);
        // 反转指针:每一个节点都执行此操作
        node.next.next = node;
        // 不用担心断开，因为后续步骤都会为node.next赋值，当前步骤保持为null就好
        node.next = null;
        return new_node;
    }

// 修改(4)的下一个节点(5)的next指针由Null指向(4)
node.next.next = node;
// 修改(4)节点的next指针由(5)指向Null 
node.next = null;

重复以上步骤，直到结束递归。

完整的Java代码如下

/**
 * @author swadian
 * @date 2022/5/8
 * @Version 1.0
 * @describetion 反转链表
 */
public class ReverseListNode {
    // 链表
    static class ListNode {
        int val; // value值
        ListNode next; // 指针
        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
        @Override
        public String toString() {
            return "(" + val + "-> " + next + ')';
        }
    }
 
    /**
     * 输入：1-2-3-4-5
     * 输出：5-4-3-2-1
     */
    public static void main(String[] args) {
        ListNode listNode = prepareListNode();
        ListNode node1 = reverseNode_1(listNode);
        ListNode node2 = reverseNode_2(listNode);
    }
 
    /**
     * 迭代思想
     * 输入：1-2-3-4-5 : (1,->2),(2,->3),(3,->4),(4,->5),(5,->null)
     * 输出：5-4-3-2-1 : (5,->4),(4,->3),(3,->2),(2,->1),(1,->null)
     */
    public static ListNode reverseNode_1(ListNode node) {
        ListNode previous = null, current, next;
        current = node;
        // 如果当前node不为空,遍历链表
        while (current != null) {
            // 保存当前节点的链接
            next = current.next;
            // 修改当前节点的链接,更改为指向之前的节点
            current.next = previous;
            // 修改之前的节点的值为当前节点
            previous = current;
            // 修改当前节点的值,继续向下遍历
            current = next;
        }
        return previous;
    }
 
    // 递归
    public static ListNode reverseNode_2(ListNode node) {
        // 终止条件和终止方法
        System.out.println(node);
        if (node == null || node.next == null) {
            return node;
        }
        // 把node替换为node.next继续向下寻找
        ListNode new_node = reverseNode_2(node.next);
        // 反转指针:每一个节点都执行此操作
        node.next.next = node;
        // 不用担心断开，因为后续步骤都会为node.next赋值，当前步骤保持为null就好
        node.next = null;
        return new_node;
    }
    
    public static ListNode prepareListNode() {
        ListNode node5 = new ListNode(5, null);
        ListNode node4 = new ListNode(4, node5);
        ListNode node3 = new ListNode(3, node4);
        ListNode node2 = new ListNode(2, node3);
        ListNode node1 = new ListNode(1, node2);
        return node1;
    }
}