第3章链表 ∥从pb链中摘下 link first-> fst>link=q;m链入结果链的链头 p=( pa I= NULL ) pa: pb; 处理未完链的剩余部分 while(p I= NULL)( q=p; p=p->link q->link first->link; first->link =9: 3-4设有一个表头指针为h的单链表。试设计一个算法,通过遍历一趟链表,将链表中所有结点的链 接方向逆转,如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点 【解答1】 template<class Type> void List<Type>: Inverse(i if( first = NULL )return; ListNode<Type> *p= first->link, *pr= NULL; while(pI=NULL )i ∥逆转frst指针 pr= first; first=p: p=p->lin ∥指针前移 first->link = pi 【解答2】 template<class Type> void List<Type>: Inverse(i ListNode<Iype>·p,head= new ListNode<Iype>();/建表头结点,其link域默认为NUIL while( first I=NULL)& p= first; first= first->link; ∥摘下fist链头结点 p->link head->link; head->link = p 插入head链前端 first= head ->link: delete head 重置frst删去表头结点 3-5从左到右及从右到左遍历一个单链表是可能的,其方法是在从左向右遍历的过程中将连接方向逆 转,如右图所示。在图中的指针p指向当前正在访问的结点,指针pr指向指针p所指结点的左侧的结 点。此时,指针p所指结点左侧的所有结点的链接方向都已逆转。 (1)编写一个算法,从任一给定的位置(p,p)开始,将指针p右移k个结点。如果p移出链表,则 将p置为0,并让pr停留在链表最右边的结点上。 (2)编写一个算法,从任一给定的位置(p,p)开始,将指针p左移k个结点。如果p移出链表,则 将p置为0,并让pr停留在链表最左边的结点上。第 3 章 链表 26 else { q = pb; pb = pb->link; } //从 pb 链中摘下 q→link = first->link; first->link = q; //链入结果链的链头 } p = ( pa != NULL ) ? pa : pb; //处理未完链的剩余部分 while ( p != NULL ) { q = p; p = p->link; q->link = first->link; first->link = q; } } 3-4 设有一个表头指针为 h 的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链 接方向逆转，如下图所示。要求逆转结果链表的表头指针 h 指向原链表的最后一个结点。 【解答 1】 template<class Type> void List<Type> :: Inverse ( ) { if ( first == NULL ) return; ListNode<Type> *p = first->link, *pr = NULL; while ( p != NULL ) { first->link = pr; //逆转 first 指针 pr = first; first = p; p = p->link; //指针前移 } first->link = pr; } 【解答 2】 template<class Type> void List<Type> :: Inverse ( ) { ListNode<Type> *p, *head = new ListNode<Type> ( ); //创建表头结点, 其 link 域默认为 NULL while ( first != NULL ) { p = first; first = first->link; //摘下 first 链头结点 p->link = head->link; head->link = p; //插入 head 链前端 } first = head->link; delete head; //重置 first, 删去表头结点 } 3-5 从左到右及从右到左遍历一个单链表是可能的，其方法是在从左向右遍历的过程中将连接方向逆 转，如右图所示。在图中的指针 p 指向当前正在访问的结点，指针 pr 指向指针 p 所指结点的左侧的结 点。此时，指针 p 所指结点左侧的所有结点的链接方向都已逆转。 (1) 编写一个算法，从任一给定的位置(pr, p)开始，将指针 p 右移 k 个结点。如果 p 移出链表，则 将 p 置为 0，并让 pr 停留在链表最右边的结点上。 (2) 编写一个算法，从任一给定的位置(pr, p)开始，将指针 p 左移 k 个结点。如果 p 移出链表，则 将 p 置为 0，并让 pr 停留在链表最左边的结点上