《算法大全-面试题-数据结构》由会员分享，可在线阅读，更多相关《算法大全-面试题-数据结构（54页珍藏版）》请在金锄头文库上搜索。
1、一、单链表目录1.单链表反转2.找出单链表的倒数第4个元素3.找出单链表的中间元素4.删除无头单链表的一个节点5.两个不交叉的有序链表的合并6.有个二级单链表，其中每个元素都含有一个指向一个单链表的指针。写程序把这个二级链表称一级单链表。7.单链表交换任意两个元素（不包括表头）8.判断单链表是否有环？如何找到环的“起始”点？如何知道环的长度？9.判断两个单链表是否相交10.两个单链表相交，计算相交点11.用链表模拟大整数加法运算12.单链表排序13.删除单链表中重复的元素首先写一个单链表的C#实现，这是我们的基石：public class Link public Link Next; publ
2、ic string Data; public Link(Link next, string data) this.Next = next; this.Data = data; 其中，我们需要人为地在单链表前面加一个空节点，称其为head。例如，一个单链表是1-2-5，如图所示：对一个单链表的遍历如下所示：static void Main(string args) Link head = GenerateLink();Link curr = head;while (curr != null) Console.WriteLine(curr.Data); curr = curr.Next; 1.单链
3、表反转这道题目有两种算法，既然是要反转，那么肯定是要破坏原有的数据结构的：算法1：我们需要额外的两个变量来存储当前节点curr的下一个节点next、再下一个节点nextnext：public static Link ReverseLink1(Link head) Link curr = head.Next; Link next = null; Link nextnext = null; /if no elements or only one element exists if (curr = null | curr.Next = null) return head; /if more than
4、 one element while (curr.Next != null) next = curr.Next; /1 nextnext = next.Next; /2 next.Next = head.Next; /3 head.Next = next; /4 curr.Next = nextnext; /5 return head;算法的核心是while循环中的5句话我们发现，curr始终指向第1个元素。此外，出于编程的严谨性，还要考虑2种极特殊的情况：没有元素的单链表，以及只有一个元素的单链表，都是不需要反转的。算法2：自然是递归如果题目简化为逆序输出这个单链表，那么递归是很简单的，在递
5、归函数之后输出当前元素，这样能确保输出第N个元素语句永远在第N+1个递归函数之后执行，也就是说第N个元素永远在第N+1个元素之后输出，最终我们先输出最后一个元素，然后是倒数第2个、倒数第3个，直到输出第1个：public static void ReverseLink2(Link head) if (head.Next != null) ReverseLink2(head.Next); Console.WriteLine(head.Next.Data); 但是，现实应用中往往不是要求我们逆序输出（不损坏原有的单链表），而是把这个单链表逆序（破坏型）。这就要求我们在递归的时候，还要处理递归后的逻
6、辑。首先，要把判断单链表有0或1个元素这部分逻辑独立出来，而不需要在递归中每次都比较一次：public static Link ReverseLink3(Link head) /if no elements or only one element exists if (head.Next = null | head.Next.Next = null) return head; head.Next = ReverseLink(head.Next); return head;我们观测到：head.Next = ReverseLink(head.Next);这句话的意思是为ReverseLink方法
7、生成的逆序链表添加一个空表头。接下来就是递归的核心算法ReverseLink了：static Link ReverseLink(Link head) if (head.Next = null) return head; Link rHead = ReverseLink(head.Next); head.Next.Next = head; head.Next = null; return rHead;算法的关键就在于递归后的两条语句：head.Next.Next = head; /1head.Next = null; /2啥意思呢？画个图表示就是：这样，就得到了一个逆序的单链表，我们只用到了1个
8、额外的变量rHead。2.找出单链表的倒数第4个元素这道题目有两种算法，但无论哪种算法，都要考虑单链表少于4个元素的情况：第1种算法，建立两个指针，第一个先走4步，然后第2个指针也开始走，两个指针步伐（前进速度）一致。static Link GetLast4thOne(Link head) Link first = head; Link second = head; for (int i = 0; i 4; i+) if (first.Next = null) throw new Exception(Less than 4 elements); first = first.Next; whil
9、e (first != null) first = first.Next; second = second.Next; return second;第2种算法，做一个数组arr4，让我们遍历单链表，把第0个、第4个、第8个第4N个扔到arr0，把第1个、第5个、第9个第4N+1个扔到arr1，把第2个、第6个、第10个第4N+2个扔到arr2，把第3个、第7个、第11个第4N+3个扔到arr3，这样随着单链表的遍历结束，arr中存储的就是单链表的最后4个元素，找到最后一个元素对应的arri，让k=(i+1)%4，则arrk就是倒数第4个元素。static Link GetLast4thOneB
10、yArray(Link head) Link curr = head; int i = 0; Link arr = new Link4; while (curr.Next != null) arri = curr.Next; curr = curr.Next; i = (i + 1) % 4; if (arri = null) throw new Exception(Less than 4 elements); return arri;本题目源代码下载：推而广之，对倒数第K个元素，都能用以上2种算法找出来。3.找出单链表的中间元素算法思想：类似于上题，还是使用两个指针first和second，
11、只是first每次走一步，second每次走两步：static Link GetMiddleOne(Link head) Link first = head; Link second = head; while (first != null & first.Next != null) first = first.Next.Next; second = second.Next; return second;但是，这道题目有个地方需要注意，就是对于链表元素个数为奇数，以上算法成立。如果链表元素个数为偶数，那么在返回second的同时，还要返回second.Next也就是下一个元素，它俩都算是单链表
12、的中间元素。下面是加强版的算法，无论奇数偶数，一概通杀：static void Main(string args) Link head = GenerateLink(); bool isOdd = true; Link middle = GetMiddleOne(head, ref isOdd); if (isOdd) Console.WriteLine(middle.Data); else Console.WriteLine(middle.Data); Console.WriteLine(middle.Next.Data); Console.Read();static Link GetMiddleOne(Link head, ref bool isOdd) Link first = head; Link second = head; while (first != null & first.Next != null
