常见算法思路小结

常见算法思路总结

1.删除单链表p指向的那个元素

有三个思路：
(1)前头结点开始查找，得到其前驱结点，然后删除，此时时间复杂度为O(n);
(2)利用双向链表，此时时间复杂度为O(1);
(3)当该结点不是链表尾部元素时，将它后面的结点值保存起来(赋给p)，删除其结点；当该结点是最后一个元素时，
从头结点遍历，此时时间复杂度为O(n),平均时间复杂度为O(1);此方法最好

**********************************************************************************************************************

2.找出两个链表的公共结点

第一种方法蛮力法：在第一链表上顺序遍历每个结点。每遍历一个结点的时候，在第二个链表上顺
序遍历每个结点，如果此时两个链表上的结点是一样的，说明此时两个链表重合，于是找到了它们的
公共结点。如果第一个链表的长度为m，第二个链表的长度为n，该方法时间复杂度为O(mn)；

第二种方法：分别遍历两个链表得到它们的长度，并求出两个长度之差。在长的链表上遍历若干次之
后，再同步遍历两个链表，直到找到相同的结点，或者一直到链表结束。此时，如果第一个链表的长
度为m，第二个链表的长度为n，该方法的时间复杂度为O(m+n).

************************************************************************************************************************

3.如何在一个字符串中查找一个字符？

(1).最简单的方法就是从头到尾扫描整个字符串，时间复杂度为O(n)
(2).由于字符的总数是有限的，对于八位的char型字符而言，总共只有256个字符，我们可以新建一个大小为
256的数组，把所有元素都初始化为0.然后对字符串中每一个字符，把它的ASCII码映射成索引，把数组中该
索引对应的元素设为1.这时候，要查找一个字符就变得很快了：根据这个字符的ASCII码，在数组中对应的下
标找到该元素，如果为0，表示字符串中没有该字符，否则包含该字符。此时，查找一个字符的时间复杂度

是O(1).其实这个数组就是一个hash表。