我们已经学习了数组，单链表，单向循环链表，双向链表，双向循环链表这五种数据结构。其中，数组我们还分别以顺序存储和链式存储的方式进行了简单的实现。接下来，我们将尝试解决七个线性表中常见的问题。

题目一 有序链表合并

将2个递增的有序链表合并为⼀个链表的有序链表; 要求结果链表仍然使⽤两个链表的存储空间, 不另外占⽤其他的存储空间. 表中不允许有重复的数据。

首先，我们要明确这两个递增的有序链表都是带有头节点的，针对于有序链表 a 和 b，可以准备两个指针 pa 和 pb 分别指向 a 和 b 的首元节点。然后判断 pa 和 pb 节点的数据域大小关系，如果 pa < pb，那么就把 pa 指向的节点保存起来，用 pc 指向 pa，然后让 pa 移动到下一个位置；如果 pb < pa，那么就把 pb 指向的节点保存起来，用 pc 指向 pb，然后让 pb 移动到下一个位置。如果 pa = pb，这里优先选择合并 pa 的节点，就让 pc 指向 pa，同时让 pa 移动到下一个位置，并且释放掉此时 pb 的指向的节点，然后让 pb 移动到下一个位置。当 pa 或 pb 中有一个链表遍历完成，比如如果 pb 遍历完成，而 pa 还有剩余节点，则直接将 pa 剩余节点附加在 pc 后面即可，然后再释放掉 pb 的头结点。接下来直接上代码:

  1. void MergeList(LinkList *La, LinkList *Lb, LinkList *Lc)
  2. {
  3.     LinkList pa,pb,pc,temp;
  4.     pa = (*La)->next;
  5.     pb = (*Lb)->next;
  6.     pc = (*Lc) = *La;
  7.     while (pa && pb)
  8.     {
  9.         if (pa->data < pb->data)
  10.         {
  11.             pc->next = pa;
  12.             pc = pa;
  13.             pa = pa->next;
  14.         }
  15.         else if (pa->data > pb->data)
  16.         {
  17.             pc->next = pb;
  18.             pc = pb;
  19.             pb = pb->next;
  20.         }
  21.         else 
  22.         {
  23.             pc->next = pa;
  24.             pc = pa;
  25.             pa = pa->next;
  27.             temp = pb;
  28.             pb = pb->next;
  29.             free(temp);
  30.         }
  31.     }
  33.     pc->next = (pa != NULL) ? pa : pb;
  35.     free(*Lb);
  37.     return OK;
  38. }

题目二 有序链表求交集

已知两个链表A和B分别表示两个集合.其元素递增排列. 设计⼀个算法,⽤于求出A与B的交集,并 存储在A链表中; 例如 : La = {2,4,6,8}; Lb = {4,6,8,10}; Lc = {4,6,8}

求链表的交集思路跟题目一差不多，不过有细微的不同。我们来分析一下

1.准备两个工作指针pa,pb 分别指向链表A和链表B的首元节点，然后声明一个指针Lc指向工作指针pc，再让pc指向链表A的头节点
2.开始寻循环遍历，循环条件为 pa 和 pb 指向的节点都不为空
2.1 判断如果 pa 和 pb 指向的节点的数据域如果相等，则将 pc 的后继指向 pa ，然后将 pc 移动到 pa，接着移动 pa 到下一个位置，最后使用一个 temp 指向 pb，让 pb 移动到下一个位置并释放掉，然后释放掉 temp
2.2 如果 pa 的数据域小于 pb，那么就使用一个 temp 指向 pa，让 pa 移动到下一个位置并释放掉，然后释放掉 temp
2.3 如果 pa 的数据域大于 pb，那么就使用一个 temp 指向 pb，让 pb 移动到下一个位置并释放掉，然后释放掉 temp
3.循环结束后再分别遍历链表A和链表B，删除掉剩余的节点
4.最后，让 pc 的后继指向 NULL

代码实现如下:

void Intersection(LinkList *La, LinkList *Lb, LinkList *Lc)
{
    LinkList pa,pb,pc,temp;
    pa = (*La)->next;
    pb = (*Lb)->next;
    *Lc = pc = *La;

    while(pa && pb)
    {
        if (pa->data == pb->data)
        {
            pc->next = pa;
            pc = pa;
            pa = pa->next;

            temp = pb;
            pb = pb->next;
            free(temp);
        }
        else if (pa->data < pb->data)
        {
            temp = pa;
            pa = pa->next;
            free(temp);
        }
        else if (pa->data > pb->data)
        {
            temp = pb;
            pb = pb->next;
            free(temp);
        }
    }

    while(pa)
    {
        temp = pa;
        pa = pa->next;
        free(temp);
    }

    while(pb)
    {
        temp = pb;
        pb = pb->next;
        free(temp);
    }

    pc->next = NULL;

    free(*Lb);

    return OK;
}

题目三 单链表反转

设计⼀个算法,将链表中所有节点的链接⽅向”原地旋转”,即要求仅仅利⽤原表的存储空间. 换句 话说,要求算法空间复杂度为O(1);

例如:L={0,2,4,6,8,10}, 逆转后: L = {10,8,6,4,2,0};

这是一道非常经典的链表反转题，题目虽然简单，但是要注意的是题目中指出只能利用原表的存储空间。解题思路主要是根据我们在前面学习过的单链表的头插法。

算法思想:
(1)利用原有的头结点*L, p为工作指针, 初始时p指向首元结点. 因为摘取的结点依次向前插入,为确保链表尾部为空,初始时将头结点的指针域置空;
(2)从前向后遍历链表,依次摘取结点,在摘取结点前需要用指针q记录后继结点,以防止链接后丢失后继结点;
(3)将摘取的结点插入到头结点之后,最后p指向新的待处理节点q(p=q);

话不多说，直接上代码:

void Inverse(LinkList *L)
{
    LinkList p, q;
    // p 指向首元节点
    p = (*L)->next;
    // 头节点的指针域置为空
    (*L)->next = NULL;
    // p 不为空的情况下进行遍历
    while (p) 
    {
        // q 指向 p 的后继节点
        q = p->next;
        // p 的后继指向 头节点指针域指向的节点
        p->next = (*L)->next;
        // 头节点的指针域指向 p
        (*L)->next = p;
        // p 指向 q，即原来 p 的后继节点
        p = q;
    }
}

题目四 删除链表指定范围的数据

设计⼀个算法,删除递增有序链表中值⼤于等于mink且⼩于等于maxk(mink,maxk是给定的两个参数,其值可以和表中的元素相同,也可以不同)的所有元素

这道题目理解题意之后就很好解决了，题目要求我们删除掉递增有序链表中 maxk>=n>=mink (n为链表的数据域的值) 范围内的数据。那么我们只需要准备两个工作指针 p 和 pre。首先先遍历一次链表，找到第一个大于 mink 的节点，然后让 p 指向该节点，让 pre 指向前一个节点，这样我们删除范围的下边界就找到了；接着我们继续遍历链表，找到第一个大于 maxk 的节点，让 p 指向这个节点。最后我们再将 pre 指向 p，这样链表就删除了指定范围内的数据，不过别忘了要释放掉这个范围内的节点。

解题思路如下:

1.查找第一个值大于 mink 的节点，用 q 指向该节点，pre 指向该节点的前驱节点 2.继续向下遍历链表，查找第一个值大于 maxk 的节点，用 p 指向该节点 3.修改下边界前驱节点的指针域，使其指向上边界 (pre->next = p) 4.依次释放待删除节点的空间(介于 pre 和 p 之间的所有节点)

void DeleteMinMax(LinkList *L, int mink, int maxk)
{
    LinkList p, q, pre;
    pre = *L;
    LinkList temp;

    // p 指向首元节点
    p = (*L)->next;

    // 查找第一个值大于 mink 的节点，用 p 指向该节点，pre 指向下边界的前驱节点
    while (p && p->data < mink)
    {
        pre = p;
        p = p->next;
    }

    // 查找第一个值大于 maxk 的节点，用 p 指向该节点，即上边界
    while (p && p->data <= maxk)
    {
        p = p->next;
    }

    // 取出下边界
    q = pre->next;

    // 将下边界的前驱指向上边界的后继，达到删除的目的
    pre->next = p;

    // 释放待删除节点
    while (q != p)
    {
        temp = q->next;
        free(q);
        q = temp;
    }
}

题目五 数组逆置

设将n(n>1)个整数存放到⼀维数组R中, 试设计⼀个在时间和空间两⽅⾯都尽可能⾼效的算法;将 R 中保存的序列循环左移p个位置(0<p<n)个位置, 即将R中的数据由(x0,x1,……,xn-1)变换为 (xp,xp+1,…,xn-1,x0,x1,…,xp-1).

例如: pre[10] = {0,1,2,3,4,5,6,7,8,9}, n = 10,p = 3; pre[10] = {3,4,5,6,7,8,9,0,1,2}

这道题目其实通过两次逆置即可求解，第一次先将 n 个数据全部逆置，然后将逆置后的数据拆分成 n-p 个 和 p 个，接着分别逆置两块数据即可得到最终的解。

解题思路:

  1. 先将n个数据原地逆置 9,8,7,6,5,4,3,2,1,0;
  2. 将n个数据拆解成[9,8,7,6,5,4,3] [2,1,0]
  3. 将前n-p个数据和后p个数据分别原地逆置; [3,4,5,6,7,8,9] [0,1,2]
void Reverse(int *pre, int left, int right)
{
    int i = left, j = right;
    int temp;
    while (i < j)
    {
        temp = pre[i];
        pre[i] = pre[j];
        pre[j] = temp
    }
}

void LeftShift(int *pre, int n, int p)
{
    if (p > 0 && p < n)
    {
        Reverse(pre, 0 , n - 1);
        Reverse(pre, 0 , n - 1 - p);
        Reverse(pre, n - p , n - 1);
    }
}

题目六 查找数组中的主元素

已知⼀个整数序列A = (a0,a1,a2,…an-1),其中(0<= ai <=n),(0<= i<=n). 若存在ap1= ap2 = …= apm = x,且m>n/2(0<=pk<n,1<=k<=m),则称x 为 A的主元素. 例如,A = (0,5,5,3,5,7,5,5),则5是主 元素; 若B = (0,5,5,3,5,1,5,7),则A 中没有主元素,假设A中的n个元素保存在⼀个⼀维数组中,请设计⼀个尽可能⾼效的算法,找出数组元素中的主元素,若存在主元素则输出该元素,否则输出-1.

这道题目需要理解主元素的定义，根据题意，所谓的主元素就是在数组中出现次数超过数组长度一半的元素。而现在既然要查找主元素，显然必须得遍历整个数组，但是题目要求要设计尽可能高效，所以不能使用双层循环这样时间复杂度很高的方式。我们冷静思考一下，我们可以分两步来完成主元素的查找工作。
第一步，先预选一个主元素，然后开始遍历数组，每当遇到和预选主元素值相等的元素就计数加一，如果不相等就减一，如果计数减为零了，那么就替换掉预选主元素为当前遍历的元素，然后以此类推。
第二步，我们得到了一个最终的预选主元素，然后再把计数置为零，然后从头开始遍历数组，计算预选主元素出现的次数是否超过了数组长度的一半，如果超过了，则返回最终的主元素，如果没有超过，则返回 -1

解题思路:

算法思路:

  1. 选取候选主元素, 从前向后依次扫描数组中的每个整数, 假定第一个整数为主元素,将其保存在Key中,计数为1. 若遇到下一个整数仍然等于key,则计数加1. 否则计数减1. 当计数减到0时, 将遇到的下一个整数保存到key中, 计数重新记为1. 开始新一轮计数. 即可从当前位置开始重上述过程,直到将全部数组元素扫描一遍;
  2. 判断key中的元素是否是真正的主元素, 再次扫描数组, 统计key中元素出现的次数,若大于n/2,则为主元素,否则,序列中不存在主元素;

算法分析:

时间复杂度: O(n)

空间复杂度: O(1)

int MainElement(int *A, int n)
{
    int count = 1;
    // 让数组的第一个元素成为预选主元素
    int key = A[0];
    int i = 0;
    // 从数组的第二个元素开始遍历数组
    for (i = 1;i < n;i++)
    {
        // 预选主元素出现了，就计数加一
        if (A[i] == key)
        {
            count++;
        }
        else 
        {
            // 预选主元素没有出现，并且计数值大于0，就计数减一
            if (count > 0) 
            {
                count--;
            }
            else
            {
                // 预选主元素没有出现，并且计数已经为零，则切换当前遍历到的元素为预选主元素
                key = A[i];
            }
        }
    }

    // 预选主元素出现次数大于 0 时再做一次检验
    if (count > 0)
    {
        // 从第一个元素开始遍历数组计数预选主元素出现的次数
        for(i = count = 0;i < n;i++)
        {
            if (A[i] == key) 
            {
                count++;
            }
        }
    }


    // 如果出现的次数大于数组长度一半，则返回主元素；否则返回 -1
    if (count > 2 / n) return key;
    else return -1;
}

题目七 删除单链表中绝对值相等的节点

⽤单链表保存m个整数, 结点的结构为(data,link),且|data|<=n(n为正整数). 现在要去设计⼀个时 间复杂度尽可能⾼效的算法. 对于链表中的data 绝对值相等的结点, 仅保留第⼀次出现的结点,⽽ 删除其余绝对值相等的结点.例如,链表A = {21,-15,15,-7,15}, 删除后的链表A={21,-15,-7};

题目中明确的说时间复杂度尽可能高效，那么我们就可以借助 「空间换时间」的思想来完成解答。这里要注意给定的 n 是大于等于链表中所有元素大小的绝对值的。
下面是解题思路:

  1. 申请 n + 1 大小的辅助空间数组 t，然后赋初值为 0。这个数组是用来记录链表中元素的值出现的次数
  2. 从链表的首元节点开始遍历，如果 t[|data|] 为 0，说明该节点之前未出现过，则保留该节点。并将 t[|data|] 的值加一；如果 t[|data|] 为 1，所以之前出现过，则删除该节点

代码实现如下:

void DeleteEqualNode(LinkList *L, int n)
{
    // 1.开辟辅助数组 p
    int *p = alloca(sizeof(int)*n);
    LinkList r = *L;

    for(int i = 0;i < n;i++)
    {
        *(p+i) = 0;
    }

    // temp 指向首元节点
    LinkList temp = (*L)->next;
    while(temp != NULL)
    {
        // 出现过，需要删除
        if (p[abs(temp->data)] == 1)
        {
            r->next = temp->next;
            free(temp);
            temp = r->next;
        }
        else 
        {
            // 没出现过，加一
            p[abs(temp->data)] = 1;
            // r 用于在删除节点的时候接上待删除节点的后继节点
            r = temp;
            // 移动 temp 到下一个位置
            temp = temp->next;
        }
    }
}