采用头插法建表的思路，用p遍历所有数据节点，先将新表看成只有一个头节点的双链表，然后将每个节点p插入该双链表的前端。算法实现如下：//有一个双链表L，其中有n（n>=1）个数据节点，设计一个算法将所有节点逆置voidReverse(DNode*&L){DNode*p=L->next,*q;L->next=NULL;while(p!=NULL)//遍历原双链表的所有数据节点{q=p->next;//用q临时保存节点p的后继节点p->next=L->next;//将节点p插入新链表的前端if(L->next!=NULL)L->next->prior=p;L->next=p;p->prior=L;p=q;//继续处理余下的节点}}

先找到第一个值为x的节点p，q指向其后继节点，如下图所示，本题时将节点p移到节点q之后，实现过程时先删除节点p,再将其插入节点q之后算法如下：//有一个双链表L，设计一个算法查找第一个值为x的节点，将其与后继结点进行交换intswap(D_LinkList&L,ElemTypex){DNode*p=L.next,*q;while(p!=NULL&&p->data!=x)//遍历节点p=p->next;if(p==NULL)//未找到值未x的节点return0;else//找到值为x的节点p{q=p->next;//q指向p的后继if(q!=NULL)//节点p不是尾节点{p->prior->next=q;//删除pq->prior=p->prior;p->next=q->next;//将节点p插入q节点之后if(q->next!=NULL)q->next->prior=p;q->next=p;p->prior=q;return1;}else//节点p是尾节点，无法与后继节点交换return0;}}

正确答案是B链表只能顺序查找定位一个元素的时间为O(N)，删除一个元素的时间为O(1)

(1)分析数据结构的本身特点，然后根据根据它本身的特点制定相应的遍历算法。(2)单链表的特点就是有多个节点组成，头指针+头结点为整个链表的开始，最后一个节点的特点是它内部的pNext指针值为NULL。从起点到结尾中间由各个节点内部的pNext指针来挂接，并且路径只有一条。(3)遍历方法：从头指针+头节点开始，顺着指针依次访问各个节点，取出各个节点的数据，直到最后一个节点，结束返回。

对于合并两个有序链表，我们可以先定义一个新链表的头节点和一个临时引用，先进行比较，哪一个链表的首位数小就把那一个作为新链表的头节点。随后，分别比较两个链表后面数据的大小，借用临时引用，把较小的一个接入新链表。此时，若一个链表为空，那可将剩下链表这部分的数据直接链入新链表。代码如下：publicstatic<TextendsComparable<T>>SingleLinkedList<T>.Node<T>mergrLinkedList(SingleLinkedList<T>.Node<T>head1,SingleLinkedList<T>.Node<T>head2){SingleLinkedList<T>.Node<T>newHead=null;//确定新链表的头节点if(head1.data.compareTo(head2.data)<0){newHead=head1;head2=head1.next;}else{newHead=head2;head2=head2.next;}//临时引用在新链表中从前往后去跑SingleLinkedList<T>.Node<T>tmp=newHead;while(head1!=null&&head2!=null){if(head1.data.compareTo(head2.data)<0){tmp.next=head1;head1=head1.next;}else{tmp.next=head2;head2=head2.next;}tmp=tmp.next;}if(head1==null){tmp.next=head2;}if(head2==null){tmp.next=head1;}returnnewHead;}

因为两个链表的长度不同，所以我们先获取两个链表的长度，让长链表的引用先走其插值的长度。随后，让两个引用同时走，若两个引用相等了，那么说明此时该引用所指向的节点即为相交结点。代码如下：publicstatic<T>SingleLinkedList<T>.Node<T>commonNode2(SingleLinkedList<T>list1,SingleLinkedList<T>list2){if(list1.head==null||list2.head==null)returnnull;//计算两个链表的差值intlength1=getlength(list1.head);intlength2=getlength(list2.head);intlengthDif=Math.abs(length1-length2);SingleLinkedList<T>.Node<T>longHead=list1.head;SingleLinkedList<T>.Node<T>shortHead=list2.head;//长链表先走其差值if(length1<length2){longHead=list1.head;shortHead=list2.head;}for(inti=0;i<lengthDif;i++){longHead=longHead.next;}//长链表和短链表开始同时走，当两个引用的相等的时候，此时该引用所指向的节点就是相交结点while(shortHead!=longHead){longHead=longHead.next;shortHead=shortHead.next;}returnlongHead;}

方式1：可以将链表反转，再逆序打印方式2：利用栈，将各个节点压入栈中，利用先入后出的特性，实现逆序打印简单测试一下栈的特性packagelinkedlist;importjava.util.Stack;publicclassTestStack{publicstaticvoidmain(String[]args){Stack<String>stack=newStack<>();//入栈stack.add("jack");stack.add("tom");stack.add("smith");//出栈while(stack.size()>0){//pop()就是将栈顶元素取出。System.out.println(stack.pop());}}}逆序打印单链表/***测试逆序打印单链表*@paramhead*/publicstaticvoidreversePrint(HeroNodehead){//空链表，不能答应if(head.next==null){return;}//创建一个栈，将各个节点压入Stack<HeroNode>stack=newStack<>();HeroNodecur=head.next;//将链表全部节点压入栈中while(cur!=null){stack.push(cur);//cur后移，可以将下一个节点压入cur=cur.next;}while(stack.size()>0){//栈的特点，先进后出System.out.println(stack.pop());}}测试逆序打印//测试逆序打印单链表System.out.println("测试逆序打印单链表");reversePrint(singleLinkedList.getHead());

首先遍历一遍，得到链表的总长度size,然后再正序遍历（size-index）得到倒数第index个节点/***查找单链表中倒数第k个节点*首先遍历一遍，得到链表的总长度size,然后再正序遍历（size-index）得到倒数第index个节点**@paramhead链表头节点*@paramindex倒数第index个节点*@return返回倒数第index个节点*/publicstaticHeroNodefindLastNode(HeroNodehead,intindex){if(head==null){returnnull;}//得到链表的长度intsize=getLength(head);//数据校验if(index>size||index<=0){returnnull;}//定义辅助变量HeroNodetargetNode=head.next;for(inti=0;i<size-index;i++){targetNode=targetNode.next;}returntargetNode;}测试//测试一下查找单链表中倒数第k个节点intindex=-1;System.out.printf("倒数第%d个节点:"+findLastNode(singleLinkedList.getHead(),index),index);

getLength方法/***统计单链表的节点的个数（不计算头节点）**@paramhead链表的头节点*@return有效节点的个数*/publicstaticintgetLength(HeroNodehead){//空链表则返回长度为0if(head.next==null){return0;}intlength=0;HeroNodecur=head.next;while(cur!=null){length++;//遍历cur=cur.next;}returnlength;}测试//测试一下求单链表中有效节点的个数System.out.println("有效节点的个数为："+getLength(singleLinkedList.getHead()));

双向链表：包含两个指针，一个prev指向前一个节点，一个next指向后一个节点。双向循环链表：最后一个节点的next指向head，而head