上一篇的MyLinkedList實現(xiàn)了一個雙向鏈表，如何對單向鏈表實現(xiàn)reverse操作呢？下面是實現(xiàn)代碼芹枷，基本思路和雙向鏈表一樣：遍歷每個節(jié)點元素，改變節(jié)點的鏈接莲趣。但是由于單向鏈表每個節(jié)點只擁有一個后繼鏈接鸳慈，所以每次操作當前遍歷的節(jié)點對象時需要額外的兩個引用pc和pn，分別指向已經反轉過的鏈表和尚未進行反轉操作的鏈表喧伞，直到pn==null退出循環(huán)走芋。

public class MySingleLinkedList<E> {
    private int size;
    private SingleNode<E> first;
    private SingleNode<E> last;

    public SingleNode<E> getLast() {
        return last;
    }

    public void setLast(SingleNode<E> last) {
        this.last = last;
    }

    public int getSize() {
        return size;
    }

    public void setSize(int size) {
        this.size = size;
    }

    public SingleNode<E> getFirst() {
        return first;
    }

    public void setFirst(SingleNode<E> first) {
        this.first = first;
    }
    //add方法
    public boolean add(E item){
        if(size<0 || size>=Integer.MAX_VALUE){
            return false;
        }
        SingleNode<E> node= new SingleNode<E>(item,null);
        if(size==0){
           first=node;
           last=node;
           size++;
        } else{
            last.setNext(node);
            last=node;
            size++;
        }
        return true;
    }
}
public class SingleNode<E> {
    E item;
    SingleNode<E> next;

    public SingleNode(E item, SingleNode<E> next) {
        this.item = item;
        this.next = next;
    }

    //省略get,set方法
}

public class MySingleLinkedListReverse<E> {
    public MySingleLinkedList<E> reverse(MySingleLinkedList<E> list){
        if(list ==null || list.getSize()<2){
            return list;
        }
        SingleNode<E> pc=list.getFirst();
        SingleNode<E> pp=null;
        SingleNode<E> pn=pc.getNext();
        while(pn!=null){
            pc.setNext(pp);
            pp=pc;
            pc=pn;
            pn=pn.getNext();
        }
        pc.setNext(pp);
        list.setLast(list.getFirst());
        list.setFirst(pc);
        return list;
    }
}

測試用例和運行結果如下

public class MySingleLinkedListTest {
    public static void main(String[] args) {
        MySingleLinkedList<Integer> list=new MySingleLinkedList<Integer>();
        for(int i=0;i<40000;i++){
            list.add(i);
        }
        Long startTime=System.currentTimeMillis();
        System.out.println("開始時間="+startTime.longValue());
       MySingleLinkedList<Integer> rList=new MySingleLinkedListReverse<Integer>().reverse(list);
       Long endTime=System.currentTimeMillis();
        System.out.println("結束時間="+endTime.longValue());
        System.out.println("單向鏈表,復用node 4萬條記錄耗時="+(endTime-startTime));
    }
}

圖片.png