《数据结构算法笔试题 算法面试笔试总结》由会员分享，可在线阅读，更多相关《数据结构算法笔试题 算法面试笔试总结（42页珍藏版）》请在金锄头文库上搜索。
1、Algorithms and Data Structures 1明确数据结构，单一进行操作1-1单一数据结构1-1-1链表在单数据结构（即在题目中明确提到了某种数据结构，没有掺杂，也没有背景，只是进行某些特定操作）的题型中，链表是一大类，而单链表因为其特定的存储结构和读取方法又成为考查的重点。列举题目如下(注：以下题目的给定Node节点全部为如下定义方式)public class Node public Node next; public object data; 1-1-1-1单链表的反转给定单链表的头节点Node head.给出将此链表反转的方法。public void ReverseLi
2、nkedList(Node head) /首先，反转后必然head为尾部节点，将head的一份拷贝赋值给一个新的node节点，用于托管旧的链表。 Node nDele = head; /等你将旧链表需要摘取的项加到新链表头部时，需要用另一个node暂时托管旧链表。 Node nNext = null; /此时就将head 置为了新链表的末尾了。 head = null; while (nDele != null) /这几部依次为：先存下当前节点的下一节点用于备份，之后将dele节点指向新链表的头部并且将新链表的头位置前移，同时控制每次循环都能指向后一个节点向前进行。 nNext = nDele
3、.next; nDele.next = head; head = nDele; nDele = nNext; /至此算法完结。在这个while循环结束时候，就将原来的链表重新接在了新链表上，完成了逆转操作。 1-1-1-2链表相交给定两个单链表，表头分别为head1和head2.判断两个链表是否相交，如果不相交返回null，如果相交，则给出相交的第一个交点。对题目进行简单分析后不难得出，因为链表的特殊存储结构，使得其在存储结构上如果交叉则一定为“Y”型或者为“V”型，不可能为“X”型。所以相交只需求出第一个交点。算法具体实现可以如下public Node FindSameNode(Node h
4、ead1, Node head2) if (head1 = null | head2 = null) return null; /两个Node用于托管两个Linkedlist，这样在操作时候不会破坏原有Node地址。 Node tNode1 = head1; Node tNode2 = head2; /用于记录两个链表的长度。 int lHead1 = 0, lHead2 = 0; /用于求出连个链表的长度， while (tNode1 != null) tNode1 = tNode1.next; lHead1+; while (tNode2 != null) tNode2 = tNode2.
5、next; lHead2+; /到最后都没有相交，必然没有相交。 if (tNode1 != tNode2) return null; /相交了，这时还可以继续从参数提取俩链表首地址。 else tNode1 = head1; tNode2 = head2;/没有这两个赋值，他们的next都为null了。 /先假设两个链表长度不一样，求出他们的长度差。 int f = System.Math.Abs(lHead1 - lHead2); /先判断后循环，小优化。 if (lHead1 lHead2) /使长的链表将长的一部分走完，之后就能一起走到交点。当循环结束，两个链表指针到末尾的长度一样了。
6、 for (int k = 0; k f; k+) tNode1 = tNode1.next; while (tNode1 != tNode2) tNode1 = tNode1.next; tNode2 = tNode2.next; /两个指针一样了，返回谁都一样。 return tNode1; else /长度相等会进此分支，只不过第一个循环不执行。其余，类似逻辑，只不过判断在外，这样代码多了，但是快一些。 for (int k = 0; k f; k+) tNode2 = tNode2.next; while (tNode1 != tNode2) tNode1 = tNode1.next;
7、 tNode2 = tNode2.next; return tNode1; 1-1-1-3链表倒数第N个节点给定一个单链表，头节点为node head.找出其倒数第N个节点。算法思路即为给定两个Node,起初在Head 节点向后走的时候，使另外一个节点node1托管这个链表的头，在Head向后走了N个节点后，node1向后遍历，在Head为Null时，node1即指向了倒数第N个节点。算法可以如下：public Node FindCountdownNode(Node head, int N) if (head = null) return null; /两个托管指针。 Node nTmpNod
8、e = head; Node nCountDownNode = head; /循环结束后，两个指针相差距离为N for (int i = 0; i N; i+) nTmpNode = nTmpNode.next; /走到结尾即可。 while (nTmpNode != null) nTmpNode = nTmpNode.next; nCountDownNode = nCountDownNode.next; return nCountDownNode; 1-1-1-4删除单个节点删除单链表中的某节点，或者不知道头节点，这时需要保证此节点不是最后一个节点，或者即使让你知道头节点，但是不允许循环遍历
9、。思路即为，因为知道这个节点，不遍历，能找到的只有他下一个节点以及他本身，这样的话将他下一个节点的数据和next属性付给当前节点，并将下一节点删除即可，偷梁换柱，达到效果。代码可以如下：public void DeleOndeNode(Node randomNode) /没有判断 Node myNext = randomNode.next; if (myNext != null) randomNode.data = myNext.data; randomNode.next = myNext.next; myNext = null; else /*只有当给定head时候才可以处理末尾节点，代码为 Node curr_node = head; while(curr_node.next!=ramdomNode) curr_node= curr_node.next; curr_node = NULL; */ 1-1-1-5链表是否有环如何判断一个链表是否有环存在。思路为定义两个指针，即好像在操场上跑步，只要两个人速度不一样，速度快的肯定会有套速度慢的一圈的时刻。难点的还可以加上找
