如何實(shí)現(xiàn)一個(gè)高效的單向鏈表逆序輸出？（詳解）

需要考慮因素，高效應(yīng)權(quán)衡多方面因素

• 數(shù)據(jù)量是否會(huì)很大
• 空間是否有限制
• 原始鏈表的結(jié)構(gòu)是否可以更改
• 時(shí)間復(fù)雜度是否有限制
• 一個(gè)鏈表節(jié)點(diǎn)需要輸出的元素有多個(gè)，例如鏈表中存的是自定義對(duì)象，有多個(gè)字段 題目。

• 01. 先學(xué)著實(shí)現(xiàn)一個(gè)簡(jiǎn)單的Java版的單項(xiàng)鏈表
  構(gòu)建任意長度的任意數(shù)值的鏈表, 頭插法,順序遍歷輸出鏈表

package com.szs.list;
/**
 * 單鏈表
 * @author Administrator
 *
 */
public class MyLinkedList {
    public int data;
    public MyLinkedList next;

    public MyLinkedList(int data) {
        this.data=data;
        this.next=null;
    }
    public MyLinkedList() {
        this.data=-1;
        this.next=null;
    }
}

02.編寫上面的單項(xiàng)鏈表的逆序輸出
高效的輸出鏈表,直接使用棧來存儲(chǔ)~~

package com.szs.list;

import java.util.Random;
import java.util.Stack;

public class InverseSingleList {

    public static void main(String[] args) {
        MyLinkedList head=  new MyLinkedList();
        createList(head);
        inverseList(head);
    }
    /**
     * 構(gòu)建任意長度的任意數(shù)值的鏈表, 頭插法
     */
    public static void createList(MyLinkedList head) {
        Random random = new Random(System.currentTimeMillis());
        int len = random.nextInt(10);
        for(int i=0;i<len;i++) {
            int data = random.nextInt(100);
            MyLinkedList next =  new MyLinkedList(data);
            next.next = head.next;
            head.next = next;
        }
        /**
         * 順序遍歷輸出鏈表
         */
        MyLinkedList head2 = head.next;
        System.out.println("順序");
        while(head2!=null) {
            System.out.print(head2.data+"\t");
            head2=head2.next;
        }
        System.out.println("length="+len);
    }
    /**
     * 高效的輸出鏈表,使用棧來存儲(chǔ)
     */
    public static void inverseList(MyLinkedList head) {
        MyLinkedList head2 = head.next;
        Stack<Integer> stack = new Stack<>();
        System.out.println("逆序");
        while(head2!=null) {
            stack.push(head2.data);
            head2=head2.next;
        }
        while(!stack.isEmpty()) {
            System.out.print(stack.pop()+"\t");
        }

    }
}

03.進(jìn)行測(cè)試

順序
25  69  10  28  23  89  32  2   23  length=9
逆序
23  2   32  89  23  28  10  69  25  
-------
順序
28  35  83  99  88  length=5
逆序
88  99  83  35  28