java 单链表反转

时间:2021-5-26 作者:qvyue

最近与人瞎聊,聊到各大厂的面试题,其中有一个就是用java实现单链表反转。闲来无事,决定就这个问题进行一番尝试。

1.准备链表

准备一个由DataNode组成的单向链表,DataNode如下:


public class DataNode {

    private int data;
    private DataNode next;
    public int getData() {
        return data;
    }
    public void setData(int data) {
        this.data = data;
    }
    public DataNode getNext() {
        return next;
    }
    public void setNext(DataNode next) {
        this.next = next;
    }
    public DataNode(int data) {
        this.data = data;
    }
}

构造链表

public class DataChain {
    
    private  DataNode head;
    
    public DataChain(int size) {
        DataNode head = new DataNode(0);
        DataNode cur = head;
        for (int i = 1; i  ");
            sb.append(cur.getNext().getData());
            cur = cur.getNext();
        }
        System.out.println(sb.toString());
    }

    public static void main(String... strings) {
        DataChain chain = new DataChain(10);
        printChain(chain.getHead());
    }
}

运行main方法,即构造了一个包含10个node节点的单链表。

#运行结果
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9

2.通过递归实现单链表反转

考虑到代码的简洁性,首先考虑的是通过递归实现。

    /**
     * 递归实现 当栈深度大于12000 则会出现StakOverflowError
     * 
     * @param head
     * @return
     */
    public static DataNode reverse1(DataNode head) {
        if (null == head || null == head.getNext())
            return head;
        DataNode revHead = reverse1(head.getNext());
        head.getNext().setNext(head);
        head.setNext(null);
        return revHead;
    }

以上即是递归实现的源码,但是需要考虑的问题是递归都在java栈中进行,需要考虑jdk支持的栈的深度。在jdk1.8.0_91版本中,当上述链表长度大于12000则会出现StackOverFlowError错误。说明对于该版本jdk栈的深度不能大于12000。

3.通过遍历实现

最通用的实现方式就是遍历。

/**
     * 遍历实现 通用实现方法
     * 
     * @param head
     * @return
     */
    public static DataNode reverse2(DataNode head) {
        if (null == head || null == head.getNext())
            return head;
        DataNode pre = head;
        DataNode cur = head.getNext();
        while (null != cur.getNext()) {
            DataNode tmp = cur.getNext();
            cur.setNext(pre);
            pre = cur;
            cur = tmp;
        }
        cur.setNext(pre);
        head.setNext(null);
        return cur;
    }

4.借助stack实现

考虑到stack具有先进后出这一特性,因此可以借助于stack数据结构来实现单向链表的反转。

/**
     * 方法3 利用其他数据结构 stack 
     * @param head
     * @return
     */
    public static DataNode reverse3(DataNode head) {
        Stack stack = new Stack();
        for (DataNode node = head; null != node; node = node.getNext()) {
            stack.add(node);
        }
        DataNode reHead = stack.pop();
        DataNode cur = reHead;
        while(!stack.isEmpty()){
            cur.setNext(stack.pop());
            cur = cur.getNext();
            cur.setNext(null);
        }
        return reHead;
    }

上述实现方法在于操作简单,对于算法并不精通的同学可以尝试。缺点在于需要通过其他数据结构实现,效率会降低,至于效率会降低到什么程度,后面举例说明。

5.三种实现方式效率分析

    public static void main(String... strings) {
        int size = 10;
        
        DataChain chain1 = new DataChain(size);
        printChain(chain1.getHead());
        long reverse1_start = System.currentTimeMillis();
        DataNode reNode1 = reverse1(chain1.getHead());
        long reverse1_cost = System.currentTimeMillis() - reverse1_start;
        printChain(reNode1);
        System.out.println("reverse1 cost time is ["+reverse1_cost+"]ms");
        
        DataChain chain2 = new DataChain(size);
        printChain(chain2.getHead());
        long reverse2_start = System.currentTimeMillis();
        DataNode reNode2 = reverse2(chain2.getHead());
        long reverse2_cost = System.currentTimeMillis() - reverse2_start;
        printChain(reNode2);
        System.out.println("reverse2 cost time is ["+reverse2_cost+"]ms");
        
        DataChain chain3 = new DataChain(size);
        printChain(chain3.getHead());
        long reverse3_start = System.currentTimeMillis();
        DataNode reNode3 = reverse3(chain3.getHead());
        long reverse3_cost = System.currentTimeMillis() - reverse3_start;
        printChain(reNode3);
        System.out.println("reverse3 cost time is ["+reverse3_cost+"]ms");
    }

执行结果:

0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0
reverse1 cost time is [0]ms
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0
reverse2 cost time is [0]ms
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0
reverse3 cost time is [1]ms

在上述代码基础上,去掉打印输出,将size改为10000,结果如下:

reverse1 cost time is [1]ms
reverse2 cost time is [0]ms
reverse3 cost time is [6]ms

可以看出reverse2 明显优于其他两种实现方法。考虑到reverse1最多只支持12000,因此将size改为100000时,再观察reverse2和reverse3之间的执行结果:

reverse2 cost time is [6]ms
reverse3 cost time is [25]ms

因此可以看出,最好的方法是采用遍历的方式进行反转。

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:qvyue@qq.com 进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。