声明本文所有13道算法题目覆盖了基本上所有常见单链表问题全都用C#实现并测试通过代码下载:TestLink.zip

 

1.单链表反转

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

3.找出单链表中间元素

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

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

6.有个 2级单链表其中每个元素都含有个指向个单链表指针写把这个 2级链表称级单链表

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

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

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

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

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

12.单链表排序

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

 

首先写个单链表C#实现这是我们基石:

public Link { public Link Next; public Data; public Link(Link next, data) { this.Next = next; this.Data = data; } }

 

其中我们需要人为地在单链表前面加个空节点称其为head例如个单链表是1->2->5如图所示:



 

对个单链表遍历如下所示:

void Main( args) { Link head = GenerateLink;

Link curr = head;

while (curr != null) { Console.WriteLine(curr.Data); curr = curr.Next; } }

 

1.单链表反转

这道题目有两种算法既然是要反转那么肯定是要破坏原有数据结构:

算法1:我们需要额外两个变量来存储当前节点curr下个节点next、再下个节点nextnext:

public Link ReverseLink1(Link head) { Link curr = head.Next; Link next = null; Link nextnext = null; // no elements or _disibledevent=> (curr null || curr.Next null) { head; } // more than _disibledevent=>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 } head; }

 

算法核心是while循环中5句话画个图来表示这5个步骤:

 

我们发现curr始终指向第1个元素

此外出于编程严谨性还要考虑2种极特殊情况:没有元素单链表以及只有个元素单链表都是不需要反转

 

算法2:自然是递归

如果题目简化为逆序输出这个单链表那么递归是很简单在递归的后输出当前元素这样能确保输出第N个元素语句永远在第N+1个递归的后执行也就是说第N个元素永远在第N+1个元素的后输出最终我们先输出最后个元素然后是倒数第2个、倒数第3个直到输出第1个:

public void ReverseLink2(Link head) { (head.Next != null) { ReverseLink2(head.Next); Console.WriteLine(head.Next.Data); } }

 

但是现实应用中往往不是要求我们逆序输出(不损坏原有单链表)而是把这个单链表逆序(破坏型)这就要求我们在递归时候还要处理递归后逻辑

首先要把判断单链表有0或1个元素这部分逻辑独立出来而不需要在递归中每次都比较次:

public Link ReverseLink3(Link head) { // no elements or _disibledevent=> (head.Next null || head.Next.Next null) head; head.Next = ReverseLink(head.Next); head; }

 

我们观测到:

head.Next = ReverseLink(head.Next);

这句话意思是为ReverseLink思路方法生成逆序链表添加个空表头

接下来就是递归核心算法ReverseLink了:

Link ReverseLink(Link head) { (head.Next null) head; Link rHead = ReverseLink(head.Next); head.Next.Next = head; head.Next = null; rHead; }

 

算法关键就在于递归后两条语句:

head.Next.Next = head; //1 head.Next = null; //2

啥意思呢？画个图表示就是:

 

这样就得到了个逆序单链表我们只用到了1个额外变量rHead

 

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

这道题目有两种算法但无论哪种算法都要考虑单链表少于4个元素情况:

第1种算法建立两个指针第个先走4步然后第2个指针也开始走两个指针步伐(前进速度)致

Link GetLast4thOne(Link head) { Link first = head; Link second = head; for ( i = 0; i < 4; i) { (first.Next null) throw Exception("Less than 4 elements"); first = first.Next; } while (first != null) { first = first.Next; second = second.Next; } second; }

 

第2种算法做个arr[4]让我们遍历单链表把第0个、第4个、第8个……第4N个扔到arr[0]把第1个、第5个、第9个……第4N+1个扔到arr[1]把第2个、第6个、第10个……第4N+2个扔到arr[2]把第3个、第7个、第11个……第4N+3个扔到arr[3]这样随着单链表遍历结束arr中存储就是单链表最后4个元素找到最后个元素对应arr[i]让k=(i+1)%4则arr[k]就是倒数第4个元素

Link GetLast4thOneByArray(Link head) { Link curr = head; i = 0; Link arr = Link[4]; while (curr.Next != null) { arr[i] = curr.Next; curr = curr.Next; i = (i + 1) % 4; } (arr[i] null) throw Exception("Less than 4 elements"); arr[i]; }

 

本题目源代码下载:

推而广的对倒数第K个元素都能用以上2种算法找出来

 

3.找出单链表中间元素

算法思想:类似于上题还是使用两个指针first和second只是first每次走步second每次走两步:

Link GetMiddleOne(Link head) { Link first = head; Link second = head; while (first != null && first.Next != null) { first = first.Next.Next; second = second.Next; } second; }

但是这道题目有个地方需要注意就是对于链表元素个数为奇数以上算法成立如果链表元素个数为偶数那么在返回second同时还要返回second.Next也就是下个元素它俩都算是单链表中间元素

下面是加强版算法无论奇数偶数概通杀:

void Main( args) { Link head = GenerateLink; bool isOdd = true; Link middle = GetMiddleOne(head, ref isOdd); (isOdd) { Console.WriteLine(middle.Data); } { Console.WriteLine(middle.Data); Console.WriteLine(middle.Next.Data); } Console.Read; } Link GetMiddleOne(Link head, ref bool isOdd) { Link first = head; Link second = head; while (first != null && first.Next != null) { first = first.Next.Next; second = second.Next; } (first != null) isOdd = false; second; }

 

4.个单链表很长遍历遍很慢我们仅知道个指向某节点指针curr而我们又想删除这个节点

这道题目是典型“狸猫换太子”如下图所示:

 

如果不考虑任何特殊情况代码就2行:

curr.Data = curr.Next.Data;
curr.Next = curr.Next.Next;

上述代码由个地方需要注意就是如果要删除是最后个元素呢？那就只能从头遍历次找到倒数第 2个节点了

 

此外这道题目个变身就是将个环状单链表拆开(即删除其中个元素)此时只要使用上面那两行代码就可以了不需要考虑表尾

相关问题:只给定单链表中某个结点p(非空结点)在p前面插入个结点q

话说交换单链表任意两个节点也可以用交换值思路方法但这样就没意思了所以才会有第7题霸王硬上工做法

 

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

有两个有序链表各自内部是有序但是两个链表的间是无序

算法思路:当然是循环逐项比较两个链表了如果个到了头就不比较了直接加上去

注意对于2个元素Data相等(仅仅是Data相等哦而不是相同引用)我们可以把它视作前面Data大于后面Data从而节省了算法逻辑

Link MergeTwoLink(Link head1, Link head2) { Link head = Link(null, Int16.MinValue); Link pre = head; Link curr = head.Next; Link curr1 = head1; Link curr2 = head2; //compare until _disibledevent=>while (curr1.Next != null && curr2.Next != null) { (curr1.Next.Data < curr2.Next.Data) { curr = Link(null, curr1.Next.Data); curr1 = curr1.Next; } { curr = Link(null, curr2.Next.Data); curr2 = curr2.Next; } pre.Next = curr; pre = pre.Next; } // head1 run to the end while (curr1.Next != null) { curr = Link(null, curr1.Next.Data); curr1 = curr1.Next; pre.Next = curr; pre = pre.Next; } // head2 run to the end while (curr2.Next != null) { curr = Link(null, curr2.Next.Data); curr2 = curr2.Next; pre.Next = curr; pre = pre.Next; } head; }

 

如果这两个有序链表交叉组成了Y型呢比如说:



这时我们需要先找出这个交叉点(图中是11)这个算法参见第9题我们这里直接使用第10道题目中思路方法GetIntersect

然后局部修改上面算法只要其中个链表到达了交叉点就直接把另个链表剩余元素都加上去如下所示:

Link MergeTwoLink2(Link head1, Link head2) { Link head = Link(null, Int16.MinValue); Link pre = head; Link curr = head.Next; Link ersect = GetIntersect(head1, head2); Link curr1 = head1; Link curr2 = head2; //compare until _disibledevent=>while (curr1.Next != ersect && curr2.Next != ersect) { (curr1.Next.Data < curr2.Next.Data) { curr = Link(null, curr1.Next.Data); curr1 = curr1.Next; } { curr = Link(null, curr2.Next.Data); curr2 = curr2.Next; } pre.Next = curr; pre = pre.Next; } // head1 run to the ersect (curr1.Next ersect) { while (curr2.Next != null) { curr = Link(null, curr2.Next.Data); curr2 = curr2.Next; pre.Next = curr; pre = pre.Next; } } // head2 run to the ersect (curr2.Next ersect) { while (curr1.Next != null) { curr = Link(null, curr1.Next.Data); curr1 = curr1.Next; pre.Next = curr; pre = pre.Next; } } head; }

 

6.有个 2级单链表其中每个元素都含有个指向个单链表指针写把这个 2级链表展开称级单链表

这个简单就是说这个 2级单链表只包括些head:

public Link { public Link Next; public Data; public Link(Link next, data) { this.Next = next; this.Data = data; } } public CascadeLink { public Link Next; public CascadeLink NextHead; public CascadeLink(CascadeLink nextHead, Link next) { this.Next = next; this.NextHead = nextHead; } }

 

下面做个 2级单链表GenerateLink1和GenerateLink2思路方法在前面都已经介绍过了:

public CascadeLink GenerateCascadeLink { Link head1 = GenerateLink1; Link head2 = GenerateLink2; Link head3 = GenerateLink1; CascadeLink element3 = CascadeLink(null, head3); CascadeLink element2 = CascadeLink(element3, head2); CascadeLink element1 = CascadeLink(element2, head1); CascadeLink head = CascadeLink(element1, null); head; }

就是说这些单链表表头head1、head2、head3、head4……它们组成了个 2级单链表head:null –> head1 –> head2 –> head3 –> head4  –>

 

我们算法思想是: 进行两次遍历在外层用curr1遍历 2级单链表head在内层用curr2遍历每个单链表:

public Link GenerateNewLink(CascadeLink head) { CascadeLink curr1 = head.NextHead; Link Head = curr1.Next; Link curr2 = Head; while (curr1 != null) { curr2.Next = curr1.Next.Next; while (curr2.Next != null) { curr2 = curr2.Next; } curr1 = curr1.NextHead; } Head; }

 

其中curr2.Next = curr1.Next.Next; 这句话是关键它负责把上个单链表表尾和下个单链表非空表头连接起来

 

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

先次遍历找到这两个元素curr1和curr2同时存储这两个元素前驱元素pre1和pre2

然后大换血

public Link SwitchPos(Link head, Link p, Link q) { (p head || q head) throw Exception("No exchange with head"); (p q) head; //find p and q in the link Link curr = head; Link curr1 = p; Link curr2 = q; Link pre1 = null; Link pre2 = null; count = 0; while (curr != null) { (curr.Next p) { pre1 = curr; count; (count 2) ; } (curr.Next q) { pre2 = curr; count; (count 2) ; } curr = curr.Next; } curr = curr1.Next; pre1.Next = curr2; curr1.Next = curr2.Next; pre2.Next = curr1; curr2.Next = curr; head; }

注意特例如果相同元素就没有必要交换；如果有个是表头就不交换

 

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

算法思想:

先分析是否有环为此我们建立两个指针从header起向前跑个步长为1个步长为2用while(直到步长2跑到结尾)检查两个指针是否相等直到找到为止

bool JudgeCircleExists(Link head) { Link first = head; //1 step each time Link second = head; //2 steps each time while (second.Next != null && second.Next.Next != null) { second = second.Next.Next; first = first.Next; (second first) true; } false; }

 

那又如何知道环长度呢？

根据上面算法在返回true地方也就是2个指针相遇处这个位置节点P肯定位于环上我们从这个节点开始先前走转了圈肯定能回来:

GetCircleLength(Link po) { length = 1; Link curr = po; while (curr.Next != po) { length; curr = curr.Next; } length; }

 

继续我们讨论如何找到环“起始”点呢？

延续上面思路我们仍然在返回true地方P计算下从有环单链表表头head到P点距离

GetLengthFromHeadToPo(Link head, Link po) { length = 1; Link curr = head; while (curr != po) { length; curr = curr.Next; } length; }

 

如果我们把环从P点“切开”(当然并不是真切那就破坏原来数据结构了)那么问题就转化为计算两个相交“单链表”交点(第10题):

个单链表是从P点出发到达P(个回圈)距离M；另个单链表从有环单链表表头head出发到达P距离N

我们可以参考第10题GetIntersect思路方法并稍作修改

private Link FindIntersect(Link head) { Link p = null; //get the po in the circle bool result = JudgeCircleExists(head, ref p); (!result) null; Link curr1 = head.Next; Link curr2 = p.Next; //length from head to p M = 1; while (curr1 != p) { M; curr1 = curr1.Next; } //circle length N = 1; while (curr2 != p) { N; curr2 = curr2.Next; } //recover curr1 & curr2 curr1 = head.Next; curr2 = p.Next; //make 2 links have the same distance to the ersect (M > N) { for ( i = 0; i < M - N; i) curr1 = curr1.Next; } (M < N) { for ( i = 0; i < N - M; i) curr2 = curr2.Next; } //goto the ersect while (curr1 != p) { (curr1 curr2) { curr1; } curr1 = curr1.Next; curr2 = curr2.Next; } null; }

 

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

这道题有多种算法

算法1:把第个链表逐项存在hashtable中遍历第2个链表每项如果能在第个链表中找到则必然相交

bool JudgeIntersectLink1(Link head1, Link head2) { Hashtable ht = Hashtable; Link curr1 = head1; Link curr2 = head2; //store all the elements of link1 while (curr1.Next != null) { ht[curr1.Next] = .Empty; curr1 = curr1.Next; } //check all the elements in link2 exists in Hashtable or not while (curr2.Next != null) { // exists (ht[curr2.Next] != null) { true; } curr2 = curr2.Next; } false; }

 

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

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

bool JudgeIntersectLink2(Link head1, Link head2) { bool exists = false; Link curr1 = head1; Link curr2 = head2; //goto the end of the link1 while (curr1.Next != null) { curr1 = curr1.Next; } //join these two links curr1.Next = head2; //iterate link2 while (curr2.Next != null) { (curr2.Next head2) { exists = true; ; } curr2 = curr2.Next; } //recover original status, whether exists or not curr1.Next = null; exists; }

 

算法3:如果两个链表末尾元素相同则必相交

bool JudgeIntersectLink3(Link head1, Link head2) { Link curr1 = head1; Link curr2 = head2; //goto the end of the link1 while (curr1.Next != null) { curr1 = curr1.Next; } //goto the end of the link2 while (curr2.Next != null) { curr2 = curr2.Next; } (curr1 != curr2) false; true; }

 

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

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

public Link GetIntersect(Link head1, Link head2) { Link curr1 = head1; Link curr2 = head2; M = 0, N = 0; //goto the end of the link1 while (curr1.Next != null) { curr1 = curr1.Next; M; } //goto the end of the link2 while (curr2.Next != null) { curr2 = curr2.Next; N; } // to the begining of the link curr1 = head1; curr2 = head2; (M > N) { for ( i = 0; i < M - N; i) curr1 = curr1.Next; } (M < N) { for ( i = 0; i < N - M; i) curr2 = curr2.Next; } while (curr1.Next != null) { (curr1 curr2) { curr1; } curr1 = curr1.Next; curr2 = curr2.Next; } null; }

 

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

例如:9>9>9>NULL + 1>NULL =>  1>0>0>0>NULL

肯定是使用递归啦不然没办法解决进位+1问题这时候要让前面节点加1而我们单链表是永远指向前

此外对于999+1=1000新得到值位数(4位)比原来两个值(1个1位1个3位)都多所以我们将表头值设置为0如果多出位来就暂时存放到表头递归结束后如果表头为1就在新链表外再加个新表头

//head1 length > head2, so M > N public Add(Link head1, Link head2, ref Link Head, M, N) { // goto the end (head1 null) 0; temp = 0; result = 0; Head = Link(null, 0); (M > N) { result = Add(head1.Next, head2, ref Head.Next, M - 1, N); temp = head1.Data + result; Head.Data = temp % 10; temp >= 10 ? 1 : 0; } // M N { result = Add(head1.Next, head2.Next, ref Head.Next, M - 1, N - 1); temp = head1.Data + head2.Data + +result; Head.Data = temp % 10; temp >= 10 ? 1 : 0; } }



这里假设head1比head2长而且M、N分别是head1和head2长度

 

12.单链表排序

无外乎是冒泡、选择、插入等排序思路方法关键是交换算法需要额外考虑第7题我编写了个交换算法在本题排序过程中我们可以在外层和内层循环里面捕捉到pre1和pre2然后进行交换而无需每次交换又要遍历次单链表

在实战中我发现冒泡排序和选择排序都要求内层循环从链表末尾向前走这明显是不合时宜

所以我最终选择了插入排序算法如下所示:

先给出基于算法:

public SortLink( .gif' />) { for ( i = 0; i < .gif' />.Length; i) { for ( j = i; j > 0; j--) { (.gif' />[j] < .gif' />[j - 1]) { //swap arr[i] and arr[lowindex] temp = .gif' />[j]; .gif' />[j] = .gif' />[j - 1]; .gif' />[j - 1] = temp; } } } .gif' />; }

 

仿照上面思想我们来编写基于Link算法:

public Link SortLink(Link head) { Link pre1 = head; Link pre2 = head.Next; Link min = null; for (Link curr1 = head.Next; curr1 != null; curr1 = min.Next) { (curr1.Next null) ; min = curr1; for (Link curr2 = curr1.Next; curr2 != null; curr2 = curr2.Next) { //swap curr1 and curr2 (curr2.Data < curr1.Data) { min = curr2; curr2 = curr1; curr1 = min; pre1.Next = curr1; curr2.Next = curr1.Next; curr1.Next = pre2; // exchange element n-1 and n, no need to add reference from pre2 to curr2, because they are the same _disibledevent=> (pre2 != curr2) pre2.Next = curr2; } pre2 = curr2; } pre1 = min; pre2 = min.Next; } head; }

 

值得注意是很多人算法不能交换相邻两个元素这是pre2和curr2是相等如果此时还执行pre2.Next = curr2; 会造成个自己引用自己环

 

交换指针很是麻烦而且效率也不高需要经常排序东西最好不要用链表来实现还是好些

 

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

用Hashtable辅助遍历遍单链表就能搞定

实战中发现curr从表头开始每次判断下个元素curr.Netx是否重复如果重复直接使用curr.Next = curr.Next.Next; 就可以删除重复元素——这是最好算法唯例外就是表尾所以到达表尾就跳出while循环

public Link DeleteDuplexElements(Link head) { Hashtable ht = Hashtable; Link curr = head; while (curr != null) { (curr.Next null) { ; } (ht[curr.Next.Data] != null) { curr.Next = curr.Next.Next; } { ht[curr.Next.Data] = ""; } curr = curr.Next; } head; }

 

 

结语:

单链表只有个向前指针Next所以要使用1-2个额外变量来存储当前元素前个或后个指针

尽量用while循环而不要用for循环来进行遍历

哇塞我就是不用指针照样能“修改地址”达到和C同样效果虽然很烦~

遍历时候不要在while循环中head=head.Next;这样会改变原先数据结构我们要这么写:Link curr=head;然后curr=curr.Next;

有时我们需要临时把环切开有时我们需要临时把单链表首尾相连成个环

究竟是玩curr还是curr.Next根据区别题目而各有用武的地没有定论不必强求