链表结构
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;
}
非递归
完整代码在这里
