单向链表的reverse实现(三)

上一篇的MyLinkedList实现了一个双向链表，如何对单向链表实现reverse操作呢？下面是实现代码，基本思路和双向链表一样：遍历每个节点元素，改变节点的链接。但是由于单向链表每个节点只拥有一个后继链接，所以每次操作当前遍历的节点对象时需要额外的两个引用pc和pn，分别指向已经反转过的链表和尚未进行反转操作的链表，直到pn==null退出循环。

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