算法面试笔试总结.doc
40墨值下载
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
ReverseLinkedList(
Node
head)
{
//
首先，反转后必然
head
为尾部节点，将
head
的一份拷贝赋值给一个新的
node
节点，
用于托管旧的链表。
Node
nDele = head;
//
等你将旧链表需要摘取的项加到新链表头部时，需要用另一个
node
暂时托管旧链
表。
Node
nNext =
null
;
//
此时就将
head
置为了新链表的末尾了。
head =
null
;
while
(nDele !=
null
)
{
//
这几部依次为：先存下当前节点的下一节点用于备份，之后将
dele
节点指向新链
表的头部并且将新链表的头位置前移，同时控制每次循环都能指向后一个节点向前进行。
nNext = nDele.next;
nDele.next = head;
head = nDele;
nDele = nNext;
}
//
至此算法完结。在这个
while
循环结束时候，就将原来的链表重新接在了新链表
上，完成了逆转操作。
}
1-1-1-2
链表相交
给定两个单链表，表头分别为
head1
和
head2.
判断两个链表是否
相交，如果不相交返回
null
，如果相交，则给出相交的第一个交
点
。
对题目进行简单分析后不难得出，因为链表的特殊存储结构，使得其在存储结构上如
果交叉则一定为“
Y
”
型或者为“
V
”
型，不可能为“
X
”
型。所以相交只需求出第一个交点。
算法具体实现可以如下
public
Node
FindSameNode(
Node
head1,
Node
head2)
{
if
(head1 ==
null
|| head2 ==
null
)
{
return
null
;
}
//
两个
Node
用于托管两个
Linkedlist
，这样在操作时候不会破坏原有
Node
地址。
Node
tNode1 = head1;
Node
tNode2 = head2;
//
用于记录两个链表的长度。
int
lHead1 = 0, lHead2 = 0;
of 43
40墨值下载
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文档的来源（墨天轮），文档链接，文档作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
下载排行榜
评论