链表 相关操作思路

 1.单链表反转

思路1：O(n^2).

       “狸猫换太子”，不进行改动链表结构，只首尾交换len/2次。但是在本函数中用到了定位函数，定位函数实际上是遍历了一遍整个链表，所以综合效率很低，达到O(n^2).

void reverseList1(Node*Head)

思路2：O(n).

       就一般的情况而言（没有之前写的辅助函数，即条件为只有Head指向一个单链表）。可以实现O（n）效率。做法是用三个相邻的指针进行遍历，在遍历的途中，更改指针方向。当然要注意链表数目分情况，和拆链的处理。

Node* reverseList2(Node*Head)

2.找出单链表的倒数第4个元素

思路1：O(2n)

        先遍历一遍链表记录节点个数。然后定位该位置count-3，定位实际上也是遍历1遍，所以总效率O(n)+O(n)

bool findLast4th1(Node*Head,int &ans)

思路2：O(n)

        如果题目限制要求，仅允许遍历一遍，则可以按如下方法进行。先定义两个指针，第一个指针先走4步，然后从这时开始，第一个指针和第二个指针同时继续走，即第一个指针和第二个指针相差4步。则第二个指针到头时，第一个指针指向倒数第四个。注意要考虑链表长度。

bool findLast4th2(Node*Head,int &ans)

思路3：O(n)

        做一个数组arr[4]，让我们遍历单链表，把第1个、第5个、第9个……第4N+1个扔到arr[0]，把第2个、第6个、第10个……第4N+2个扔到arr[1]，把第3个、第7个、第11个……第4N+3个扔到arr[2]，把第4个、第8个、第12个……第4N个扔到arr[3]，这样随着单链表的遍历结束，arr中存储的就是单链表的最后4个元素，找到最后一个元素对应的arr[i]，让k=(i+1)%4，则arr[k]就是倒数第4个元素。如果不易理解，画个图就好了。注意增加的空间只需要4个，所以是常数级的。比如加到第5个节点时就会把arr[0]中的值冲掉。

bool findLast4th3(Node*Head,int &ans)

3.找出单链表的中间元素

思路1：O(2n)

         在函数的支持下，直接求整个链表的长度，然后定位中间元素。

bool getMiddleOne1(Node*Head,int&ans)

思路2：O(n)

        如果仍要求只遍历一遍。类似于上题，还是使用两个指针first和second，只是first每次走一步，second每次走两步：

bool getMiddleOne2(Node*Head,int&ans)

4.删除无头单链表的一个节点

思路：

         注意这里的要求是无头链表，即未知Head指针。但是知道的是current指针指向该链表的某一位置。现在希望删除该指针，而不影响整个链表。即虽然不知道Head指针，但是该链还是完整的。

        首先需要明确一点，即current指针之前的链表段落是不可能知道的。这是由链表的单向性决定的。没有任何技术可以做到这一点。

        其次，删除链表某节点，该节点不能是首节点，因为首节点一旦删除，Head无法找到该链表了。

        再次，删除链表某节点，该节点不能是尾节点，因为尾节点一旦删除，则尾节点的前一节点的指针域无法置0（因为单链无法回溯）。

        所以题意解释为：删除无头单链表的一个节点（既非首节点也非尾节点）。

        解法是利用“狸猫换太子”。首先复制current指针的下一个节点的value到current节点中。然后删除current的下一节点。

void deleteNoHeadList(Node* Head,Node*Current)

4+.增加无头单链表的一个节点，一个指针current指向单链表中的一个节点，在该节点之前增加一个节点insertNode。

思路：

         思路还是“狸猫换太子”，即在current之后增加一个节点insertNode，然后交换insertNode和current的值。

         由于在current之后增加节点这个操作在current指向首尾都可以实现。

         所以这道问题转化为：增加无头单链表的一个节点，current指针指向该链表某节点（可以为首尾），在其之前增加节点p。

void addNoHeadList(Node*Head,Node*Current,Node*insertNode)

5.两个不交叉的有序链表的合并

思路：O(len1+len2)

        合并的办法如下，首先用Node*& 方式传入两个链表的头指针Head1，Head2。用指针引用是因为最后要修改Head1和Head2均为NULL。否则可能被其他人误引用了。然后定义一个合并后的链表的头指针和尾指针Head和Tail。然后不断比较Head1和Head2的首元素，加入到新的合并的链表中。注意一点这里的加入并不是先增加申请一个节点分配，然后删除释放原来的节点。而是直接将指针指向。也就是说在合并的过程中只是指针指向改变了，完全没有申请新的内存和释放节点空间。最后如果有一个Head1或Head2的已经空了，则直接将剩余链表连接到Head即可。当然要注意很多细节。

Node* mergeTwoList(Node*& Head1,Node*& Head2)

6.有个二级单链表，其中每个元素都含有一个指向一个单链表的指针。写程序把这个二级链表称一级单链表。

思路：

        注意要重新定义二级单链表的结构，具体的算法是：把所有的下级单链表顺次连接。即可。程序代码略。

7.单链表交换任意两个元素（不包括表头）

思路：

          利用“狸猫换太子”，不破坏链表结构，只交换二者Node* cur1和Node* cur2的指向的值。程序代码略。

          其中的任意两个元素由外界给定该两个节点的指针。

8.判断单链表是否有环（6形状）？如何找到环的“起始”点？如何知道环的长度？

思路：

        注意分析题意，题意并非是说单链表完全成O形状的环，而是说单链表成6形状的环。

        首先判断是否有环：为此我们建立两个指针，从Head一起向前跑，一个步长为1，一个步长为2，用

  while(直到步长2的跑到结尾)
{
检查两个指针是否相等，直到找到为止。
}

来进行判断。

            原因是，在这场跑步中，结束循环有两种可能，其一是原来无环，所以2先跑到结尾，因为2比1快，二者不可能相等。其二是原来是有环的，因为这场赛跑永远没有z终点，但是在环中，由于2比1快，因而必定套圈，也即2追上了1，这在无环中是不可能出现的情况。

           而进行计算环的长度，只要找到交汇点，然后在圈中跑一次就可以了。

int getCircleLength(Node* cross)

bool judgeCircleExists(Node* Head)

9.判断两个单链表是否相交

            注意这里是判断是否相交。对于判断问题来讲，相对还是比较简单的。注意单链表并非不能有重复元素。

思路1：O(len1*len2)

            把第一个链表的指针值逐项存在hashtable中，遍历第2个链表的每一项的指针值，如果能在第一个链表中找到，则必然相交。但是C++的STL模板中的hash不太会用。所以我使用了set集合，不过貌似set集合是使用遍历的方式来查找元素是否在集合中的，所以效率是比较低的，至少在O(len1*len2)级别。

bool judgeIntersectList1(Node* Head1,Node* Head2)

思路2：O(len1+len2)

          把一个链表A接在另一个链表B的末尾，如果有环，则必然相交。如何判断有环呢？从A开始遍历，如果能回到A的表头，则肯定有环。

注意，在返回结果之前，要把刚才连接上的两个链表断开，恢复原状。

bool judgeIntersectList2(Node* Head1,Node* Head2)

思路3：O（len1+len2）

         如果两个链表的末尾元素相同（指针相同，即为同一个元素，而非值相等），则必相交。
bool judgeIntersectList3(Node* Head1,Node* Head2)

10.两个单链表相交，计算相交点

思路1：

         分别遍历两个单链表，计算出它们的长度M和N，假设M比N大，则长度M的链表先前进M-N，然后两个链表同时以步长1前进，前进的同时比较当前的元素，如果相同，则必是交点。
Node* getIntersectPoint(Node* Head1,Node* Head2)

思路2：

         将指针p1,p2定位到两个链表的尾部，然后同时将两个指针前移（不可以，因为是单向链表）

11.用链表模拟大整数加法运算

思路：

        对于高精度大数计算，没有数组那么高效，具体数组的做法参见OJ高精度，链表的好处是可以定义节点，其中包含指数次数和值两部分，比如20001可以表示为(2,4)->(1,0)->NULL其中2表示值，4表示10的4次方。这样的话如果数属于稀疏型的则以较少的空间保存了值。具体程序略。

12.单链表排序

思路：

         参见基本函数13：//冒泡排序链表，具体的做法是“狸猫换太子”，即只交换节点中的值，对链表结构不做改动。

void sortList(Node*& Head);

13.删除单链表中重复的元素

思路：

         用Hashtable辅助，遍历一遍单链表就能搞定。同高级函数9的原因，我不太会使用C++STL中的hash。而如果使用set集合来存储链表中的所有的值，实际上效率和每次重新遍历单链表是一样的。“用了c++标准库中的set来保存访问过的元素，所以很方便的就可以判断当前节点是否在set集合中，直接使用set提供的find函数就可以了。而且使用set的查找在时间复杂度上比较低。”我不太清楚STL中set集合的实现方式，如果是基于类似hash结构的话，那自然效率O(1),而如果是数组的话，实际在遍历一遍，所以效率O(n)。不过貌似后者的可能性大一些。

void DeleteDuplexElements(Node*Head);