Java单链表反转

当前位置:

首页 > 编程开发 > Java教程 >

Java单链表反转

博客前言

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

这篇文章主要记录一下单链表反转

回到顶部

v定义链表

/**
 * @author toutou https://www.cnblogs.com/toutou/
 * @date by 2020/11
 * @des
 */
public class ListNode {
    public int value;
    public ListNode next;

    public ListNode(int data){
        this.value = data;
    }
}

回到顶部

v递归实现

/**
 * @author toutou https://www.cnblogs.com/toutou/
 * @date by 2020/11
 * @des
 */
public class ReverseHelper {
    public static ListNode reverse(ListNode curr){
        if(curr == null || curr.next == null){
            return curr;
        }

        ListNode temp = curr.next;
        ListNode newNode = reverse(curr.next);
        temp.next = curr;
        curr.next = null;
        return newNode;
    }
}

回到顶部

v非递归实现

/**
 * @author toutou https://www.cnblogs.com/toutou/
 * @date by 2020/11
 * @des
 */
public class ReverseHelper {
    public static ListNode whileReverse(ListNode curr){
        ListNode pre = null;
        ListNode next = null;
        while(curr != null){
            next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }

        return pre;
    }
}

回到顶部

v测试效果

/**
 * @author toutou https://www.cnblogs.com/toutou/
 * @date by 2020/11
 * @des
 */
public class App {
    public static void main(String[] args) {
        ListNode head = new ListNode(0);
        ListNode tmp = null;
        ListNode cur = null;
        for (int i = 1; i < 10; i++) {
            tmp = new ListNode(i);
            if (1 == i) {
                head.next = tmp;
            } else {
                cur.next = tmp;
            }
            cur = tmp;
        }

        // ListNode node1 =ReverseHelper.whileReverse(head);
        ListNode node1 =ReverseHelper.reverse(head);
        while (node1!= null){
            System.out.println(node1.value);
            node1 = node1.next;
        }

        System.out.println("OK");
    }
}

回到顶部

v源码地址

https://github.com/toutouge/javademosecond/tree/master/hellospringboot

出处：https://www.cnblogs.com/toutou/p/reverse_list.html

栏目列表