C++面试题-链表栈二叉树数据结构

一、单链表

目录

1.单链表反转

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

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

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

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

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

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

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

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

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

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

12.单链表排序

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

 

 

首先写一个单链表的C#实现，这是我们的基石：

public class Link

{

    public Link Next;

    public 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.单链表反转

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

算法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 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：自然是递归

如果题目简化为逆序输出这个单链表，那么递归是很简单的，在递归函数之后输出当前元素，这样能确保输出第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);

    }

}

 

 

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

首先，要把判断单链表有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方法生成的逆序链表添加一个空表头。

接下来就是递归的核心算法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;  //1

head.Next = null;       //2

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

 

 

这样，就得到了一个逆序的单链表，我们只用到了1个额外的变量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;

    }

    while (first != null)

    {

        first = first.Next;

        second = second.Next;

    }

    return 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个元素。

static Link GetLast4thOneByArray(Link head)

{

    Link curr = head;

    int i = 0;

    Link[] arr = new Link[4];

    while (curr.Next != null)

    {

        arr[i] = curr.Next;

        curr = curr.Next;

        i = (i + 1) % 4;

    }

    if (arr[i] == null)

        throw new Exception("Less than 4 elements");

    return arr[i];

}

 

 

本题目源代码下载：

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

 

 

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

算法思想：类似于上题，还是使用两个指针first和second，只是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也就是下一个元素，它俩都算是单链表的中间元素。

下面是加强版的算法，无论奇数偶数，一概通杀：

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)

    {

        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;

}

 

 

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

 

 

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

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

然后大换血

public static Link SwitchPoints(Link head, Link p, Link q)

{

    if (p == head || q == head)

        throw new Exception("No exchange with head");

    if (p == q)

        return head;

    //find p and q in the link

    Link curr = head;

    Link curr1 = p;

    Link curr2 = q;

    Link pre1 = null;

    Link pre2 = null;

 

    int count = 0;

while (curr != null)

    {

        if (curr.Next == p)

        {

            pre1 = curr;

            count++;

            if (count == 2)

                break;

        }

        else if (curr.Next == q)

        {

            pre2 = curr;

            count++;

            if (count == 2)

                break;

        }

        curr = curr.Next;

    }

    curr = curr1.Next;

    pre1.Next = curr2;

    curr1.Next = curr2.Next;

    pre2.Next = curr1;

    curr2.Next = curr;

    return head;

}

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

 

 

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

算法思想：

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

static 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;

        if (second == first)

            return true;

    }

    return false;

}

 

 

那又如何知道环的长度呢？

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

static int GetCircleLength(Link point)

{

    int length = 1;

    Link curr = point;

    while (curr.Next != point)

    {

        length++;

        curr = curr.Next;