单链表反转

链表结构

class MyList{
    public int val;
    public MyList next;
    public MyList(int val){
        this.val=val;
    }
}

递归和非递归实现都基于下面这张图的原理,不同的是,递归时从后向前,非递归是从前向后,并且非递归要head进行额外处理

CD转换

递归实现示意

 public static MyList recursiveReverse(MyList head){
        if(head==null||head.next==null)
            return head;
        MyList reversedList=recursiveReverse(head.next);
        head.next.next=head;

        head.next=null;
        return reversedList;
    }

递归

非递归示意

public static MyList nonRecursiveReverse(MyList head){
        MyList prev=head;
        MyList cur=head.next;
        MyList nex;
        while(cur!=null){
            nex=cur.next;
            //下面这句是错的,想想为什么
            //prev.next=null;
            cur.next=prev;

            prev=cur;
            cur=nex;

        }
        head.next=null;
        return prev;
    }

非递归

完整代码在这里