思想：

①　给出算法的基本设计思想:算法的策略是从前向后扫描数组元繁，杯记出一个可能成为主元素的元素Num。然后重新计数，确认 Num是否是主元素。算法可分为以下两步:（摩尔投票法）

（1) 选取候选的主元素。依次扫描所给数组中的每个整数，将第一个遇到的整数Num保存到c中，记录 Num 的出现次数为1;若遇到的下一个整数仍等于 Num，则计数加1，否则计数减1:当计数减到0时,将遇到的下一个整数保存到c中，计数重新记为1，开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部数组元素

（2) 判断c中元素是否是真正的主元素。再次扫描该数组，统计c中元素出现的次数，若大于n/2，则为主元素:否则，序列中不存在主元素

8. 给定一个含n(n≥I)个整数的数组，请攻订一个杜时间一公马)向效的算法，找出数组中未出现的最小正整数。例如，数组{-5,3,2,3}中未出现的最小正整数是l;数组{1,2,3}中未出现的最小正整数是4

思想：

①　要求在时间上尽可能高效，因此采用空问换时间的办法。分配一个用于标记的数组B[n]用来记录A中是否出现了1~n中的正整数，B[0]对应正整数1，B[n-1]对应正整数n，初始化B中全部为0。由于A中含有n个整数，因此可能返回的值是 1_{n+1，当A中n个数恰好为1}n 时返回n+1。当数组A中出现了小于等于0或大于n的值时,会导致1~~n中出现空余位置，返回结果必然在1~n中，因此对于A中出现了小于等于0或大于n的值,可以不采取任何操作

②　经过以上分析可以得出算法流程:从A[0]开始遍历A,若0

9. 定义三元组(a, b,c)(a、b、c均为正数）的距离D=a-b+|b-c+Ic - a。给定3个非空整数集合S、S2和S,按升序分别存储在3个数组中。请设计一个尽可能高效的算法，计算并输出所有可能的三元组(a, b,c) (aES,bES, cES）中的最小距离。例如S={H1, 0, 9}, S={-25,-10, 10,11}SJ={2,9,17, 30, 41}，则最小距离为2，相应的三元组为(9, 10, 9)

思想：

2）链表经典题目的编程思想

1. 设计一个递归算法，删除不带头结点的单链表L中所有值为×的结点

思想：

①　设f(L,x)的功能是删除以工为首结点指针的单链表中所有值等于x的结点，显然有f(L->next,x)的功能是删除以L->next为首结点指针的单链表中所有值等于x的结点。由此,可以推出递归模型如下。

（1) 终止条件:f(L,x)=不做任何事情; 若L为空表

（2) 递归主体:f(L, x)=删除*L结点;f(L->next, x); 若L->data==X

（3) :f(L,x)=f(L->next, x); 其他情况

2. 在带头结点的单链表L中，删除所有值为×的结点,并释放其空间假设值为×的结点不唯一，试编写算法以实现上述操作

思想：

①　采用尾插法建立单链表。用p指针扫描工的所有结点，当其值不为x时，将其链接到L之后，否则将其释放

3. 试编写算法将带头结点的单链表就地逆置，所谓“就地”是指辅助空间复杂度为O(1)

思想：

①　将头结点摘下，然后从第一结点开始，依次插入到头结点的后面(头插法建立单链表)，直到最后一个结点为止，这样就实现了链表的逆置

4. 给定两个单链表，编写算法找出两个链表的公共结点

思想：

①　先把问题简化:如何判断两个单向链表有没有公共结点?应注意到这样:一个事实:若两个链表有一个公共结点，则该公共结点之后的所有结点都是重合的，即它们的最后一个结点必然是重合的。因此，我们判断两个链表是不是有重合的部分时，只需要分别遍历两个链表到最后一个结点。若两个尾结点是:一样的，则说明它们有公共结点，否则两个链表没有公共结点。

②　然而，在上面的思路中，顺序遍历两个链表到尾结点时，并不能保证在两个链表上同时到达尾结点。这是因为两个链表长度不一定一样。但假设一个链表比另一个长k个结点，我们先在长的链表上遍历k个结点，之后再同步遍历，此时我们就能保证同时到达最后一个结点。由于两个链表从第一个公共结点开始到链表的尾结点，这一部分是重合的，因此它们肯足也是同时到达第一公共结点的。于是在遍历中，第一个相同的结点就是第一个公共的结点。

③　根据这一思路中，我们先要分别遍历两个链表得到它们的长度，并求出两个长度之差。在长的链表上先遍历长度之差个结点之后，再同步遍历两个链表，直到找到相同的结点，或者一直到链表结束。此时，该方法的时间复杂度为 O(len1 + len2)

5. 已知两个链表A和B分别表示两个集合，其元素递增排列。编制函数、求A与B的交集，并存放于A链表中

思想：

①　算法思想:采用归并的思想,设置两个工作指针pa和pb,对两个链表进行归并扫描，只有同时出现在两集合中的元素才链接到结果表中且仅保留一个，其他的结点全部释放。当一个链表遍历完毕后，释放另一个表中剩下的全部结点（链表归并类型的试题在各学校历年真题中出现的频率很高）

6.

思想：

①　问题的关键是设计一个尽可能高效的算法,通过链表的一次遍历，找到倒数第k个结点的位置。算法的基本设计思想是:定义两个指针变盘p和q，初始时均指向头结点的下一个结点(链表的第一个结点)p指针沿链表移动;当指针移动到第k个结点时，4指针开始与p指针同步移动;当指针移动到最后一个结点时，指针所指示结点为倒数第k个结点。以上过程对链表仅进行一遍扫描

7.

思想：

①　算法的核心思想是用空间换时间。使用辅助数组记录链表中已出现的数值，从而只需对链表进行一趟扫描。因为|datal≤n,故辅助数组q的大小为n+1，各元素的初值均为0。依次扫描链表中的各结点，同时检查q[ldatal]的值，若为0则保留该结点，并令q[ldatal]=1;否则将该结点从链表中删除

②　用哈希表：设长度为n+1的数组，每次插入一个元素因元素值与数组下标相同故在数组相应位置置为1，若检测为1则删除当前结点，反之为0插入且置为1

8. 设计一个算法完成以下功能:判断一个链表是否有环，如果有，找出环的入口点并返回,否则返回NULL

思想：

①　（快慢指针也可作为求表长一半的方法)

9. 设线性表L=(a_1,a_2,…,a_(n-1),a_n)采用带头结点的单链表保存,链表中的结点定义如下:

typedef struct node

{int data;

struct node*next;

}NODE;

请设计一个空间复杂度为O(1)且时间上尽可能高效的算法，重新排列L中的各结点，得到线性表L'=(a_1,a_n,a_2,a_(n-1),a_3,a(n-2),…)

思想：

①　先观察L=(a_1,a_2,…,a_(n-1),a_n)和L'=(a_1,a_n,a_2,a_(n-1),a_3,a(n-2),…)，发现L'是由L摘取第一个元素，再摘取倒数第一个元素……依次合并而成的。为了方便链表后半段取元素，需要先将L后半段原地逆置[题目要求空间复杂度为O(1)，不能借助栈],否则每取最后一个结点都需要遍历一次链表

（1) 先找出链表L的中间结点，为此设置两个指针p和q,指针p每次走一步，指针q每次走两步,当指针q到达链尾时,指针p正好在链表的中间结点

（2) 然后将L的后半段结点原地逆置

（3) 从单链表前后两段中依次各取一个结点