p=(pa I= NULL ) pa: pb; 处理未完链的剩余部分 while(p I= NULL )i q→link=irst→link;mrst→link=q; 3-6设有一个表头指针为h的单链表。试设计一个算法,通过遍历一趟链表,将链表中所有结点的链 接方向逆转,如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。 h 【解答1】 template<class Type> void Lisk<Type>: Immerse ()i if(first== NULL)return; Listooder<Type>·p=fst→lik;,spr=NULL; ile(p I= NULL)i 逆转st指针 =p;p=p→link 指针前移 【解答2】 template<class Type> void Lis<<Type>: Inverse()i ListNode<Type> ' p, head new ListNode<Type>(; while (first I= NULL)& p=first; first =first-link 摘下fst链头结点 p→link=head→link;head→lnk=p;/插入head链前端 first head-link; delete head ∥重置fst 3-7从左到右及从右到左遍历一个单链表是可能的,其方法是在从左向右遍历的过程中将连接方向逆 转,如右图所示。在图中的指针p指向当前正在访问的结点,指针p指向指针p所指结点的左侧的结 点。此时,指针p所指结点左侧的所有结点的链接方向都已逆转 (1)编写一个算法,从任一给定的位置(pr,p)开始,将指针p右移k个结点。如果p移出链表,则 将p置为0,并让p停留在链表最右边的结点上。 (2)编写一个算法,从任一给定的位置(p,p)开始,将指针p左移k个结点。如果p移出链表,则 将p置为0,并让pr停留在链表最左边的结点上 【解答】 (1)指针p右移k个结点p = ( pa != NULL ) ? pa : pb; //处理未完链的剩余部分 while ( p != NULL ) { q = p; p = p→link; q→link = first→link; first→link = q; } } 3-6 设有一个表头指针为 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; //指针前移 } } 【解答 2】 template<class Type> void List<Type> :: Inverse ( ) { ListNode<Type> *p, *head = new ListNode<Type> ( ); while ( first != NULL ) { p = first; first = first→link; //摘下 first 链头结点 p→link = head→link; head→link = p; //插入 head 链前端 } first = head→link; delete head; //重置 first } 3-7 从左到右及从右到左遍历一个单链表是可能的，其方法是在从左向右遍历的过程中将连接方向逆 转，如右图所示。在图中的指针 p 指向当前正在访问的结点，指针 pr 指向指针 p 所指结点的左侧的结 点。此时，指针 p 所指结点左侧的所有结点的链接方向都已逆转。 (1) 编写一个算法，从任一给定的位置(pr, p)开始，将指针 p 右移 k 个结点。如果 p 移出链表，则 将 p 置为 0，并让 pr 停留在链表最右边的结点上。 (2) 编写一个算法，从任一给定的位置(pr, p)开始，将指针 p 左移 k 个结点。如果 p 移出链表，则 将 p 置为 0，并让 pr 停留在链表最左边的结点上。 【解答】 (1) 指针 p 右移 k 个结点