(1)反转一个链表。循环算法。
List reverse(List n) {
if(!n) {
return n; }
list cur = n.next; list pre = n;
list tmp;
//判断链表是否为空,为空即退出。
//保存头结点的下个结点 //保存头结点

pre.next = null;
while ( NULL != cur.next ) {
tmp = cur; tmp.next = pre pre = tmp;
cur = cur.next;
//头结点的指针指空,转换后变尾结点 //循环直到 cur.next 为空
//实现如图 10.3—图 10.5 所示
}
return tmp; //f 返回头指针
}
(2)反转一个链表。递归算法。
List *reverse( List *oldList, List *newHead = NULL ) {
List *next = oldList-> next; oldList-> next = newHead; newHead = oldList;
//记录上次翻转后的链表 //将当前结点插入到翻转后链表的开头 //递归处理剩余的链表
return ( next==NULL )? newHead: reverse( t, newHead );
}
说明:循环算法就是图 10.2—图 10.5 的移动过程,比较好理解和想到。递归算法的设计虽有一点难 度,但是理解了循环算法,再设计递归算法就简单多了。
