算法大全-面试题-数据结构

{

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) {

first = first.Next.Next; second = second.Next; }

if (first != null) isOdd = false; return second; }

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

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

如果不考虑任何特殊情况，代码就2行： curr.Data = curr.Next.Data;

curr.Next = curr.Next.Next;

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

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

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

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

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

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

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

注意，对于2个元素的Data相等（仅仅是Data相等哦，而不是相同的引用），我们可以把它视作前面的Data大于后面的Data，从而节省了算法逻辑。 static Link MergeTwoLink(Link head1, Link head2) {

Link head = new Link(null, Int16.MinValue); Link pre = head;

Link curr = head.Next; Link curr1 = head1; Link curr2 = head2;

//compare until one link run to the end

while (curr1.Next != null && curr2.Next != null) {

if (curr1.Next.Data < curr2.Next.Data) {

curr = new Link(null, curr1.Next.Data); curr1 = curr1.Next; } else {

curr = new Link(null, curr2.Next.Data); curr2 = curr2.Next; }

pre.Next = curr; pre = pre.Next; }

//if head1 run to the end while (curr1.Next != null) {

curr = new Link(null, curr1.Next.Data); curr1 = curr1.Next; pre.Next = curr; pre = pre.Next; }

//if head2 run to the end

while (curr2.Next != null) {

curr = new Link(null, curr2.Next.Data); curr2 = curr2.Next; pre.Next = curr; pre = pre.Next; }

return head; }

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

这时我们需要先找出这个交叉点（图中是11），这个算法参见第9题，我们这里直接使用第10道题目中的方法GetIntersect。 然后局部修改上面的算法，只要其中一个链表到达了交叉点，就直接把另一个链表的剩余元素都加上去。如下所示：

static Link MergeTwoLink2(Link head1, Link head2) {

Link head = new Link(null, Int16.MinValue); Link pre = head;

Link curr = head.Next;

Link intersect = GetIntersect(head1, head2); Link curr1 = head1; Link curr2 = head2;

//compare until one link run to the intersect

while (curr1.Next != intersect && curr2.Next != intersect) {

if (curr1.Next.Data < curr2.Next.Data) {

curr = new Link(null, curr1.Next.Data); curr1 = curr1.Next; } else {

curr = new Link(null, curr2.Next.Data); curr2 = curr2.Next; }

pre.Next = curr; pre = pre.Next; }

//if head1 run to the intersect if (curr1.Next == intersect) {

while (curr2.Next != null) {

curr = new Link(null, curr2.Next.Data); curr2 = curr2.Next; pre.Next = curr; pre = pre.Next; } }

//if head2 run to the intersect else if (curr2.Next == intersect) {

while (curr1.Next != null) {

curr = new Link(null, curr1.Next.Data); curr1 = curr1.Next; pre.Next = curr; pre = pre.Next; } }

return head; }

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

这个简单，就是说，这个二级单链表只包括一些head： public class Link {

public Link Next; public int Data;

public Link(Link next, int data) {

this.Next = next; this.Data = data; } }

public class CascadeLink {

public Link Next;

public CascadeLink NextHead;

public CascadeLink(CascadeLink nextHead, Link next)

{

this.Next = next;

this.NextHead = nextHead; } }

下面做一个二级单链表，GenerateLink1和GenerateLink2方法在前面都已经介绍过了：

public static CascadeLink GenerateCascadeLink() {

Link head1 = GenerateLink1(); Link head2 = GenerateLink2(); Link head3 = GenerateLink1();

CascadeLink element3 = new CascadeLink(null, head3);

CascadeLink element2 = new CascadeLink(element3, head2); CascadeLink element1 = new CascadeLink(element2, head1); CascadeLink head = new CascadeLink(element1, null); return head; }

就是说，这些单链表的表头head1、head2、head3、head4??，它们组成了一个二级单链表head：null –> head1 –> head2 –> head3 –> head4 –>

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

public static Link GenerateNewLink(CascadeLink head) {

CascadeLink curr1 = head.NextHead; Link newHead = curr1.Next; Link curr2 = newHead; while (curr1 != null) {

curr2.Next = curr1.Next.Next; while (curr2.Next != null) {

curr2 = curr2.Next; }

curr1 = curr1.NextHead; }

return newHead; }