一、线性表的顺序表示

01.从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。

bool Del_Min(SqList &L, ElemType &value) {
    //删除顺序表 L 中最小值元素结点，并通过引用型参数 value 返回其值
    //若删除成功，则返回 true；否则返回 false
    if (L.length == 0)
        return false;                //表空，中止操作返回
    value = L.data[0];
    int pos = 0;                     //假定 0 号元素的值最小
    for (int i = 1; i < L.length; i++)  //循环，寻找具有最小值的元素
        if (L.data[i] < value) {     //让value记忆当前具有最小值的元素
            value = L.data[i];
            pos = i;
        }
    L.data[pos] = L.data[L.length - 1];  //空出的位置由最后一个元素填补
    L.length--;
    return true;                     //此时，value为最小值
}

02.设计一个高效算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为O(1)。

void Reverse(SqList &L){
    ElemType temp;
    for(int i = 0 ; i<L.length/2 ;i++){
        temp = L.data[i];
        L.data[i] = L.data[L.length-i-1];
        L.data[L.length-i-1] = temp;
    }
}

03.对长度为n的顺序表L，编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除顺序表中所有值为x的数据元素。

void del_x_1(SqList &L, ElemType x) {
    //本算法实现删除顺序表 L 中所有值为 x 的数据元素
    int k=0, i;                     //记录值不等于 x 的元素个数
    for (i=0; i<L.length; i++)
        if (L.data[i] != x) {
            L.data[k] = L.data[i];
            k++;                    //不等于 x 的元素增 1
        }
    L.length = k;                   //顺序表 L 的长度等于 k
}

void del_x_2(SqList &L, ElemType x) {
    int k=0, i=0;                   //k 记录值等于 x 的元素个数
    while (i < L.length) {
        if (L.data[i] == x)
            k++;
        else
            L.data[i - k] = L.data[i];  //当前元素前移 k 个位置
        i++;
    }
    L.length = L.length - k;        //顺序表 L 的长度递减
}

04.从顺序表中删除其值在给定值s和t之间（包含s和t，要求s<t）的所有元素，若s或t不合理或顺序表为空，则显示出错信息并退出运行

bool Del_s_t(SqList &L, ElemType s, ElemType t) {
    //删除顺序表 L 中值在给定值 s 和 t（要求 s<t）之间的所有元素
    int i, k = 0;
    if (L.length == 0 || s >= t)
        return false;                //线性表为空或 s、t 不合法，返回
    for (i = 0; i < L.length; i++) {
        if (L.data[i] >= s && L.data[i] <= t)
            k++;
        else
            L.data[i - k] = L.data[i];  //当前元素前移 k 个位置
    } //for
    L.length -= k;                   //长度减小
    return true;
}

05.从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同

bool Delete_Same(SeqList& L) {
    if (L.length == 0)
        return false;

    int i, j;                     //i 存储第一个不相同的元素，j 为工作指针
    for (i = 0, j = 1; j < L.length; j++)
        if (L.data[i] != L.data[j])  //查找下一个与上一个元素值不同的元素
            L.data[++i] = L.data[j]; //找到后，将元素前移

    L.length = i + 1;
    return true;
}

06.将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表

bool Merge(SeqList A, SeqList B, SeqList &C) {
    //将有序顺序表 A 与 B 合并为一个新的有序顺序表 C
    if (A.length + B.length > C.maxSize)  //大于顺序表的最大长度
        return false;
    int i = 0, j = 0, k = 0;
    while (i < A.length && j < B.length) {  //循环，两两比较，小者存入结果表
        if (A.data[i] <= B.data[j])
            C.data[k++] = A.data[i++];
        else
            C.data[k++] = B.data[j++];
    }
    while (i < A.length)  //还剩一个没有比较完的顺序表
        C.data[k++] = A.data[i++];
    while (j < B.length)
        C.data[k++] = B.data[j++];
    C.length = k;
    return true;
}

07.已知在一维数组A[m+n]中依次存放两个线性表(a1,a2,a3...,am)和(b1,b2,b3..,bn)。编写一个函数，将数组中两个顺序表的位置互换，即将(b1,b2,b3,...,bn)放在(a1,a2,a3,...,am)的前面。

//算法思想：首先将数组 A[m+n]中的全部元素
//(a₁, a₂, a₃, …, aₘ, b₁, b₂, b₃, …, bₙ)原地逆置为
//(bₙ, bₙ₋₁, bₙ₋₂, …, b₁, aₘ, aₘ₋₁, aₘ₋₂, …, a₁)，
//然后对前 n 个元素和后 m 个元素分别使用逆置算法，
//即可得到(b₁, b₂, b₃, …, bₙ,a₁, a₂, a₃, …, aₘ)，
//从而实现顺序表的位置互换。

typedef int DataType;
void Reverse(DataType A[],int left,int right,int arraySize){
//逆转(a[left],a[left+1],a[left+2],…,a[right])为(a[right],a[right-1],…,a[left])
    if(left>=right||right>=arraySize)
        return;
    int mid=(left+right)/2;
    for(int i=0;i<=mid-left;i++){
        DataType temp=A[left+i];
        A[left+i]=A[right-i];
        A[right-i]=temp;
    }
}
void Exchange(DataType A[],int m,int n,int arraySize){
/*数组 A[m+n]中，从 0 到 m-1 存放顺序表(a1,a2,a3,…,am)，从 m 到 m+n-1 存放顺序表
(b1,b2,b3,…,bn)，算法将这两个表的位置互换*/
    Reverse(A,0,m+n-1,arraySize);
    Reverse(A,0,n-1,arraySize);
    Reverse(A,n,m+n-1,arraySize);
}

08.线性表(a1,a2,a3,..，an)中的元素递增有序且按顺序存储于计算机内。要求设计一个算法，完成用最少时间在表中查找数值为x的元素，若找到，则将其与后继元素位置相交换，若找不到，则将其插入表中并使表中元素仍递增有序。

//算法思想
//顺序存储的线性表递增有序，可采用顺序查找或折半查找，
//题目要求用最少的时间查找数值为x的元素，因此选用折半查找法。

void SearchExchangeInsert(ElemType A[],ElemType x){
    int low=0,high=n-1,mid;        //low和high指向顺序表下界和上界的下标
    while(low<=high){
        mid=(low+high)/2;                //找中间位置
        if(A[mid]==x) break;            //找到x，退出while循环
        else if(A[mid]<x) low=mid+1;    //到中点mid的右半部去查
        else high=mid-1;                //到中点mid的左半部去查
    }
    //下面两个if语句只会执行一个
    if(A[mid]==x&&mid!=n-1){            //若最后一个元素与x相等，则不存在与其后继交换的操作
        t=A[mid]; A[mid]=A[mid+1]; A[mid+1]=t;
    }
    if(low>high){                       //查找失败，插入数据元素x
        for(i=n-1;i>high;i--) A[i+1]=A[i]; //后移元素
        A[i+1]=x;                       //插入x
    }                                   //结束插入
}

09.给定三个序列A、B、C，长度均为n，且均为无重复元素的递增序列，请设计一个时间上尽可能高效的算法，逐行输出同时存在于这三个序列中的所有元素。例如，数组A为{1,2,3}，数组B为{2,3,4}，数组C为{-1,0,2}，则输出2。要求:
1)给出算法的基本设计思想。
2)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
3)说明你的算法的时间复杂度和空间复杂度。

1）算法的基本设计思想。
使用三个下标变量从小到大遍历数组。当三个下标变量指向的元素相等时，
输出并向前推进指针，否则仅移动小于最大元素的下标变量，直到某个下标变量移出数组范围，即可停止。

2）算法的实现。
void samekey(int A[],int B[],int C[],int n){
    int i=0,j=0,k=0;        //定义三个工作指针
    while(i<n&&j<n&&k<n){   //相同则输出，并集体后移
        if(A[i]==B[j]&&B[j]==C[k]){
            printf("%d\n",A[i]);
            i++;j++;k++;
        }else{
            int maxNum=max(A[i],max(B[j],C[k]));
            if(A[i]<maxNum) i++;
            if(B[j]<maxNum) j++;
            if(C[k]<maxNum) k++;
        }
    }
}


3）每个指针移动的次数不超过n次，且每次循环至少有一个指针后移，
所以时间复杂度为O(n)，算法只用到了常数个变量，空间复杂度为O(1)。

10.

1）算法的基本设计思想：

可将问题视为把数组ab转换成数组ba（a代表数组的前p个元素，b代表数组中余下的n−p个元素），
先将a逆置得到a⁻¹b，再将b逆置得到a⁻¹b⁻¹，最后将整个a⁻¹b⁻¹逆置得到(a⁻¹b⁻¹)⁻¹= ba。
设Reverse函数执行将数组逆置的操作，对abcdefgh向左循环移动3（p=3）个位置的过程如下：
Reverse(0,p−1)得到cbadefgh；
Reverse(p,n−1)得到cbahgfed；
Reverse(0,n−1)得到defghabc。
注：在Reverse中，两个参数分别表示数组中待转换元素的始末位置。


2）使用C语言描述算法如下：
void Reverse(int R[],int from,int to) {
    int i,temp;
    for(i=0;i<(to-from+1)/2;i++){
    temp=R[from+i];
    R[from+i]=R[to-i];
    R[to-i]=temp;
  }
}
void Converse(int R[],int n,int p) {
    Reverse(R,0,p-1);
    Reverse(R,p,n-1);
    Reverse(R,0,n-1);
}


3）上述算法中三个Reverse函数的时间复杂度分别为O(p/2)、O((n−p)/2)和O(n/2)，
故所设计的算法的时间复杂度为O(n)，空间复杂度为O(1)。

11.

1）算法的基本设计思想如下：
分别求两个升序列A、B的中位数，设为a和b，求序列A、B的中位数过程如下：
① 若a = b，则a或b为所求中位数，算法结束。
② 若a < b，则舍弃序列A中较小的一半，同时舍弃序列B中较大的一半，要求两次舍弃的长度相等。
③ 若a > b，则舍弃序列A中较大的一半，同时舍弃序列B中较小的一半，要求两次舍弃的长度相等。
在保留的两个升序序列中，重复过程①、②、③，
直到两个序列中均只含一个元素时为止，较小者为所求的中位数。


2）本题代码如下：
int M_Search(int A[],int B[],int n){
    int s1,d1,m1,s2,d2,m2;
    s1=0;d1=n-1;
    s2=0;d2=n-1;
    while(s1!=d1 || s2!=d2){
        m1=(s1+d1)/2;
        m2=(s2+d2)/2;
        if(A[m1]==B[m2])
            return A[m1];        //满足条件①
        if(A[m1]<B[m2]){        //满足条件②
            if((s1+d1)%2==0){   //若元素个数为奇数
                s1=m1;          //舍弃A中间点以前的部分，且保留中间点
                d2=m2;          //舍弃B中间点以后的部分，且保留中间点
            }
            else{               //元素个数为偶数
                s1=m1+1;        //舍弃A的前半部分
                d2=m2;          //舍弃B的后半部分
            }
        }
        else{                   //满足条件③
            if((s1+d1)%2==0){   //若元素个数为奇数
                d1=m1;          //舍弃A中间点以后的部分，且保留中间点
                s2=m2;          //舍弃B中间点以前的部分，且保留中间点
            }
            else{               //元素个数为偶数
                d1=m1;          //舍弃A的后半部分
                s2=m2+1;        //舍弃B的前半部分
            }
        }
    }
    return A[s1]<B[s2]? A[s1]:B[s2];
}

3）算法的时间复杂度为O(log2 n)，空间复杂度为O(1)。

注：两个数组都是升序的，我们不用看全部数字，只需要「互相比较、砍掉无用的一半」，直到最后只剩 2 个数比大小。为什么能这么砍？举个例子你就懂：比如 A 数组中位数是 3，B 数组中位数是 7 → 因为数组都是从小到大排的，A 里比 3 小的数，肯定都太小了，不可能是最终的中位数；B 里比 7 大的数，肯定都太大了，也不可能是最终的中位数。所以我们可以直接把 A 的小半边、B 的大半边一起砍掉！砍掉后剩下的 A 和 B，长度还是一样的，然后在剩下的部分里，继续重复「比中位数、砍一半」的操作。砍到最后，两个数组里都只剩 1 个数字了，这两个数里，小的那个就是我们要的最终中位数

12.

//主元素：这个数在列表里出现的次数，得超过列表长度的一半。
//摩尔投票法
//如果数组中存在主元素，那么这个元素的「势力」足够强 —— 它和其他所有元素一对一抵消后，
//最后一定还能剩下；如果没有主元素，抵消到最后也会剩下一个「假候选」，需要后续验证。
1）算法的基本设计思想：算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素Num。
然后重新计数，确认Num是否是主元素。
算法可分为以下两步：
① 选取候选的主元素：依次扫描所给数组中的每个整数，将第一个遇到的整数Num保存到c中，
记录Num的出现次数为1；若遇到的下一个整数仍等于Num，则计数加1，否则计数减1；
当计数减到0时，将遇到的下一个整数保存到c中，计数重新记为1，开始新一轮计数，
即从当前位置开始重复上述过程，直到扫描完全部数组元素。
② 判断c中元素是否是真正的主元素：再次扫描该数组，统计c中元素出现的次数，
若大于n/2，则为是主元素；否则，序列中不存在主元素。

2）算法实现如下：
int Majority(int A[],int n){
    int i,c,count=1;        //c用来保存候选元素，count用来计数
    c=A[0];                 //设置A[0]为候选主元素
    for(i=1;i<n;i++)        //查找候选主元素
        if(A[i]==c)
            count++;        //对A中的候选主元素计数
        else
            if(count>0)
                count--;    //处理不是候选主元素的情况
            else{
                c=A[i];     //更换候选主元素，重新计数
                count=1;
            }
    if(count>0)
        for(i=0,count=0;i<n;i++) //统计候选主元素的实际出现次数
            if(A[i]==c)
                count++;
    if(count>n/2) return c; //确认候选主元素
    else return -1;         //不存在主元素
}

3）实现的程序的时间复杂度为O(n)，空间复杂度为O(1)。

注：本题若采用先排序再统计的方法（时间复杂度为O(nlogn)），则只要解答正确，最高可拿11分。
即便是写出O(n²)的算法，最高也能拿10分，
因此对于统考算法题，花费大量时间去思考最优解法是得不偿失的。
本算法的方法非常典型，需牢固掌握。

13.

1）算法的基本设计思想：
要求在时间上尽可能高效，因此采用“空间换时间”的办法。
分配一个用于标记的数组B[n]，用来记录A中是否出现了1~n中的正整数，
B[0]对应正整数1，B[n-1]对应正整数n，初始化B中全部为0。
A中含有n个整数，因此可能返回的值是1~n+1，当A中n个数恰好为1~n时返回n+1。
当数组A中出现了小于或等于0或大于n的值时，会导致1~n中出现空余位置，返回结果必然在1~n中，
因此对于A中出现了小于或等于0或大于n的值，可以不采取任何操作。
经过以上分析可以得出算法流程：
从A[0]开始遍历A，若0<A[i]≤n，则令B[A[i]-1]=1；否则不做操作。
对A遍历结束后，开始遍历数组B，
若能查找到第一个满足B[i]==0的下标i，返回i+1即为结果，此时说明A中未出现的最小正整数在1和n之间。
若B[i]全部不为0，返回i+1（跳出循环时i=n，i+1等于n+1），此时说明A中未出现的最小正整数是n+1。


2）算法实现：
int findMissMin(int A[], int n)
{
    int i, *B; //标记数组
    B = (int *)malloc(sizeof(int)*n); //分配空间
    memset(B, 0, sizeof(int)*n); //赋初值为0
    for (i=0; i<n; i++)
        if (A[i]>0 && A[i]<=n) //若A[i]的值介于1~n，则标记数组B
            B[A[i]-1] = 1;
    for (i=0; i<n; i++) //扫描数组B，找到目标值
        if (B[i]==0) break;
    return i+1; //返回结果
}

3）时间复杂度： 遍历A一次，遍历B一次，两次循环内操作步骤为O(1)量级，因此时间复杂度为O(n)。
空间复杂度： 额外分配了B[n]，空间复杂度为O(n)。

14.

15.

二、线性表的链式表示

01. 在带头结点的单链表L中，删除所有值为x的结点，并释放其空间，假设值为x的结点不唯一，试编写算法以实现上述操作。

//解法1: 用p从头到尾扫描单链表，pre指向*p结点的前驱。
//若p所指结点的值为x，则删除，并让p移向下一个结点，
//否则让pre、p指针同步后移一个结点。
void Del_X_1(Linklist &L,ElemType x){
    LNode *p=L->next,*pre=L,*q;//置p和pre的初始值
    while(p!=NULL){
        if(p->data==x){
            q=p;                //q指向被删结点
            p=p->next;
            pre->next=p;        //将*q结点从链表中断开
            free(q);            //释放*q结点的空间
        }
        else{                   //否则，pre和p同步后移
            pre=p;
            p=p->next;
        }//else
    }//while
}

//本算法是在无序单链表中删除满足某种条件的所有结点，这里的条件是结点的值为x。
//实际上，这个条件是可以任意指定的，只要修改if条件即可。
//比如，我们要求删除值介于mink和maxk之间的所有结点，
//则只需将if语句修改为`if(p->data>=mink&&p->data<=maxk)`。


//解法2: 采用尾插法建立单链表。
//用p指针扫描L的所有结点，当其值不为x时，将其链接到L之后，否则将其释放。

void Del_X_2(Linklist &L,ElemType x){
    LNode *p=L->next,*r=L,*q;  //r指向尾结点，其初值为头结点
    while(p!=NULL){
        if(p->data!=x){        //*p结点值不为x时将其链接到L尾部
            r->next=p;
            r=p;
            p=p->next;         //继续扫描
        }
        else{                  //*p结点值为x时将其释放
            q=p;
            p=p->next;         //继续扫描
            free(q);           //释放空间
        }
    }//while
    r->next=NULL;              //插入结束后置尾结点指针为NULL
}

//上述两个算法扫描一遍链表，时间复杂度为O(n)，空间复杂度为O(1)。

02. 试编写在带头结点的单链表L中删除一个最小值结点的高效算法（假设该结点唯一）。

LinkList Delete_Min(LinkList &L) {
    LNode *pre=L, *p=pre->next;  //p为工作指针，pre指向其前驱
    LNode *minpre=pre, *minp=p;  //保存最小值结点及其前驱
    while(p!=NULL){
        if(p->data < minp->data){
            minp=p;              //找到比之前找到的最小值结点更小的结点
            minpre=pre;
        }
        pre=p;                   //继续扫描下一个结点
        p=p->next;
    }
    minpre->next=minp->next;     //删除最小值结点
    free(minp);
    return L;
}

03. 试编写算法将带头结点的单链表就地逆置，所谓“就地”是指辅助空间复杂度为O(1)。

LinkList Reverse_1(LinkList L){
    LNode *p, *r;          //p为工作指针，r为p的后继，以防断链
    p=L->next;             //从第一个元素结点开始
    L->next=NULL;          //先将头结点L的next域置为NULL
    while(p!=NULL){        //依次将元素结点摘下
        r=p->next;         //暂存p的后继
        p->next=L->next;   //将p结点插入到头结点之后
        L->next=p;
        p=r;
    }
    return L;
}

LinkList Reverse_2(LinkList L) {
    LNode *pre, *p=L->next, *r=p->next;
    p->next=NULL;              //处理第一个结点
    while(r!=NULL) {           //r为空，则说明p为最后一个结点
        pre=p;                 //依次继续遍历
        p=r;
        r=r->next;
        p->next=pre;           //指针反转
    }
    L->next=p;                 //处理最后一个结点
    return L;
}

04. 设在一个带表头结点的单链表中，所有结点的元素值无序，试编写一个函数，删除表中所有处于给定的两个值（作为函数参数给出）之间的元素（若存在）。

void LNode *Delete(LinkList &L, int min, int max){
    LinkList pr=L,p=L->link;     //p是检测指针，pr是其前驱
    while(p!=NULL)
    {
        if(p->data>min&&p->data<max){ //寻找到被删结点，删除
            pr->link=p->link;
            free(p);
            p=pr->link;
        }else{                    //否则继续寻找被删结点
            pr=p;
            p=p->link;
        }
    }
}

05. 给定两个单链表，试分析找出两个链表的公共结点的思想（不用写代码）。

    两个单链表有公共结点，即两个链表从某一结点开始，它们的next都指向同一结点。
每个单链表结点只有一个next域，因此从第一个公共结点开始，之后的所有结点都是重合的，
不可能再出现分叉。所以两个有公共结点而部分重合的单链表，拓扑形状看起来像Y，而不可能像X。
    本题极容易联想到“蛮”方法：在第一个链表上顺序遍历每个结点，每遍历一个结点，
在第二个链表上顺序遍历所有结点，若找到两个相同的结点，则找到了它们的公共结点。
显然，该算法的时间复杂度为O(len1×len2)。
    接下来我们试着去寻找一个线性时间复杂度的算法。先把问题简化：如何判断两个单链表有没有公共结点？
应注意到这样一个事实：
若两个链表有一个公共结点，则该公共结点之后的所有结点都是重合的，即它们的最后一个结点必然是重合的。
因此，我们判断两个链表是不是有重合的部分时，只需要分别遍历两个链表到最后一个结点。
若两个尾结点是一样的，则说明它们有公共结点，否则两个链表没有公共结点。
    然而，在上面的思路中，顺序遍历两个链表到尾结点时，并不能保证在两个链表上同时到达尾结点。
这是因为两个链表长度不一定一样。
但假设一个链表比另一个长k个结点，我们先在长的链表上遍历k个结点，之后再同步遍历，此时我们就能保证同时到达最后一个结点。
从第一个公共结点开始到链表的尾结点，这一部分是重合的，因此它们肯定也是同时到达第一公共结点的。
于是在遍历中，第一个相同的结点就是第一个公共的结点。
    根据这一思路中，我们先要分别遍历两个链表得到它们的长度，并求出两个长度之差。
在长的链表上先遍历长度之差个结点之后，再同步遍历两个链表，直到找到相同的结点，或者一直到链表结束。
此时，该方法的时间复杂度为O(len1 + len2)。

06. 设C={a₁,b₁,a₂,b₂,…,aₙ,bₙ}为线性表，采用带头结点的单链表存放，设计一个就地算法，将其拆分为两个线性表，使得A={a₁,a₂,…,aₙ}，B={bₙ,…,b₂,b₁}。

//循环遍历链表C，采用尾插法将一个结点插入表A，这个结点为奇数号结点，
//这样建立的表A与原来的结点顺序相同；
//采用头插法将下一结点插入表B，这个结点为偶数号结点，
//这样建立的表B与原来的结点顺序正好相反。

LinkList DisCreat_2(LinkList &A) {
    LinkList B=(LinkList)malloc(sizeof(LNode));//创建B表表头
    B->next=NULL;              //B表的初始化
    LNode *p=A->next,*q;       //p为工作指针
    LNode *ra=A;               //ra始终指向A的尾结点
    while(p!=NULL){
        ra->next=p; ra=p;      //将*p链到A的表尾
        p=p->next;
        if(p!=NULL){
            q=p->next;         //头插后，*p将断链，因此用q记忆*p的后继
            p->next=B->next;   //将*p插入到B的前端
            B->next=p;
            p=q;
        }
    }
    ra->next=NULL;             //A尾结点的next域置空
    return B;
}

//该算法特别需要注意的是，采用头插法插入结点后，*p 的指针域已改变，
//若不设变量保存其后继结点，则会引起断链，从而导致算法出错。

注：

// 定义拆分函数：返回链表B的头指针，参数A是原链表C的头结点（引用传递，修改的是原链表）
LinkList DisCreat_2(LinkList &A) {
    // 1. 给链表B创建头结点（申请内存，大小为一个链表结点）
    LinkList B=(LinkList)malloc(sizeof(LNode));
    // 2. 初始化B链表：头结点后面暂时没有元素，next指向空
    B->next=NULL;              
    // 3. 定义工作指针p（初始指向A头结点的下一个结点，即原链表第一个元素a₁），临时指针q（后续记路用）
    LNode *p=A->next,*q;       
    // 4. 定义ra指针（始终指向A的尾结点，方便尾插法），初始指向A的头结点
    LNode *ra=A;               
    // 5. 循环遍历原链表：只要p没走到链表末尾（p≠NULL），就继续处理
    while(p!=NULL){
        // 6. 尾插法：把p指向的奇数位结点（a₁/a₂/...）加到A的末尾
        ra->next=p;  // 让A当前尾结点的next指向p，把p接在A最后
        ra=p;        // 更新ra为新的尾结点（刚插入的p）
        // 7. p往后挪一步，指向原链表的下一个结点（偶数位结点b₁/b₂/...）
        p=p->next;
        // 8. 检查p是否为空（避免原链表最后只剩奇数位结点，没有偶数位结点的情况）
        if(p!=NULL){
            // 9. 关键：用q记住p的下一个结点（因为头插法会改p的next，不记路会“迷路”）
            q=p->next;         
            // 10. 头插法第一步：让p的next指向B头结点当前的下一个结点（把p接在B现有元素前面）
            p->next=B->next;   
            // 11. 头插法第二步：让B头结点的next指向p，p成为B的第一个元素
            B->next=p;
            // 12. p回到q记录的位置（原链表中bₙ的下一个aₙ₊₁），继续遍历
            p=q;
        }
    }
    // 13. 给A收尾：A的尾结点ra的next置空，避免A后面还连无用结点
    ra->next=NULL;             
    // 14. 返回拆分后的链表B
    return B;
}

07. 在一个递增有序的单链表中，存在重复的元素。设计算法删除重复的元素，例如 (7, 10, 10, 21, 30, 42, 42, 42, 51, 70) 将变为 (7,10,21,30,42,51,70)。

//题中链表是有序表，因此所有相同值域的结点都是相邻的。用p扫描递增单链表L，
//若*p结点的值域等于其后继结点的值域，则删除后者，否则p移向下一个结点
void Del_Same(LinkList &L){
    LNode *p=L->next,*q;       //p为扫描工作指针
    if(p==NULL)
        return;
    while(p->next!=NULL){
        q=p->next;             //q指向*p的后继结点
        if(p->data==q->data){  //找到重复值的结点
            p->next=q->next;   //释放*q结点
            free(q);           //释放相同元素值的结点
        }
        else
            p=p->next;
    }
}

08. 设A和B是两个单链表（带头结点），其中元素递增有序。设计一个算法从A和B中的公共元素产生单链表C，要求不破坏A、B的结点。

void Get_Common(LinkList A, LinkList B) {
    LNode *p=A->next, *q=B->next, *r, *s;
    LinkList C = (LinkList)malloc(sizeof(LNode));  //建立表C
    r=C;                                           //r始终指向C的尾结点
    while(p!=NULL&&q!=NULL){                       //循环跳出条件
        if(p->data<q->data)
            p=p->next;                             //若A的当前元素较小，后移指针
        else if(p->data>q->data)
            q=q->next;                             //若B的当前元素较小，后移指针
        else{                                      //找到公共元素结点
            s=(LNode*)malloc(sizeof(LNode));       //复制产生结点*s
            s->data=p->data;
            r->next=s;                             //将*s链接到C上（尾插法）
            r=s;
            p=p->next;                             //表A和B继续向后扫
            q=q->next;
        }
    }
    r->next=NULL;                                  //置C尾结点指针为空
}

09. 已知两个链表A和B分别表示两个集合，其元素递增排列。编制函数，求A与B的交集，并存放到A链表中。

LinkList Union(LinkList &la, LinkList &lb) {
    LNode *pa=la->next;        //设工作指针分别为pa和pb
    LNode *pb=lb->next;
    LNode *pc=la;              //结果表中当前合并结点的前驱指针pc
    while(pa&&pb) {
        if(pa->data==pb->data) { //交集并入结果表中
            pc->next=pa;         //A中结点链接到结果表
            pc=pa;
            pa=pa->next;
            u=pb;
            pb=pb->next;
            free(u);             //B中结点释放
        }
        else if(pa->data<pb->data) { //若A中当前结点值小于B中当前结点值
            u=pa;
            pa=pa->next;        //后移指针
            free(u);            //释放A中当前结点
        }
        else{                   //若B中当前结点值小于A中当前结点值
            u=pb;
            pb=pb->next;        //后移指针
            free(u);            //释放B中当前结点
        }
    }//while结束
    while(pa) {                 //B已遍历完，A未完
        u=pa;
        pa=pa->next;
        free(u);                //释放A中剩余结点
    }
    while(pb) {                 //A已遍历完，B未完
        u=pb;
        pb=pb->next;
        free(u);                //释放B中剩余结点
    }
    pc->next=NULL;              //置结果链表尾指针为NULL
    free(lb);                   //释放B表的头结点
    return la;
}

10. 两个整数序列A=a1,a2,a3,...,am和B=b1,b2,b3,...,bn已经存入两个单链表中，设计一个算法，判断序列B是否是序列A的连续子序列。

int Pattern(LinkList A,LinkList B){
    //pre记A链表的工作指针，本题假定A和B均无头结点
    LNNode *pre=A;
    //pre记住每趟比较中A链表的开始结点
    LNNode *p=pre;
    LNNode *q=B;
    //q是B链表的工作指针
    while (p&&q)
    {
        if(p->data==q->data) //结点值相同
        {
            p=p->next;
            q=q->next;
        }
        else{
            pre=pre->next;
            p=pre;         //A链表新的开始比较结点
            q=B;           //q从B链表第一个结点开始
        }
    }
    if(q==NULL)             //B已经比较结束
        return 1;           //说明B是A的子序列
    else
        return 0;           //B不是A的子序列
}

11. 设计一个算法用于判断带头结点的循环双链表是否对称。

int Symmetry(DLinkList L){
    DNNode *p=L->next, *q=L->prior;  //两头工作指针
    while (p!=q && p->next!=q)       //循环跳出条件
    {
        if (p->data==q->data) {      //所指结点值相同则继续比较
            p=p->next;
            q=q->prior;
        }
        else                         //否则，返回0
            return 0;
    }
    return 1;                        //比较结束后返回1
}

12. 有两个循环单链表，链表头指针分别为h1和h2，编写一个函数将链表h2链接到链表h1之后，要求链接后的链表仍保持循环链表形式。

LinkList Link(LinkList h1, LinkList h2) {
    //将循环链表h2链接到循环链表h1之后，使之仍保持循环链表的形式
    LNode *p, *q;              //分别指向两个链表的尾结点
    p=h1;
    while(p->next!=h1)        //寻找h1的尾结点
        p=p->next;
    q=h2;
    while(q->next!=h2)        //寻找h2的尾结点
        q=q->next;
    p->next=h2;               //将h2链接到h1之后
    q->next=h1;               //令h2的尾结点指向h1
    return h1;
}

13. 设有一个带头结点的非循环双链表L，其每个结点中除有pre、data和next域外，还有一个访问频度域freq，其值均初始化为零。每当在链表中进行一次Locate(L,x)运算时，令值为x的结点中freq域的值增1，并使此链表中的结点保持按访问频度递减的顺序排列，且最近访问的结点排在频度相同的结点之前，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L,x)函数，返回到结点的地址，类型为指针型。

DLinkList Locate(DLinkList &L,ElemType x){
    DNode *p=L->next,*q;      //p为工作指针，q为p的前驱，用于查找插入位置
    while (p&&p->data!=x)     //查找值为x的结点
        p=p->next;
    if (!p)                   //不存在值为x的结点
        exit(0);
    else{
        p->freq++;            //令元素值为x的结点的freq域加1
        if (p->pre==L||p->pre->freq>p->freq)
            return p;         //p是链表首结点，或freq值小于前驱
        if (p->next!=NULL) p->next->pre=p->pre;
        p->pre->next=p->next; //将p结点从链表上摘下
        q=p->pre;             //以下查找p结点的插入位置
        while (q!=L&&q->freq<=p->freq)
            q=q->pre;
        p->next=q->next;
        if (q->next!=NULL) q->next->pre=p; //将p结点排在同频率的第一个
        p->pre=q;
        q->next=p;
    }
    return p;                 //返回值为x的结点的指针
}

14. 设将n(n>1)个整数存放到不带头结点的单链表L中，设计算法将L中保存的序列循环右移k(0<k<n)个位置。例如，若k=1，则将链表{0,1,2,3}变为{3,0,1,2}。要求： 1）给出算法的基本设计思想。 2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。 3）说明你所设计算法的时间复杂度和空间复杂度。

2）
LNode *Convert(LNode *L,int k){
    int n=1;                //n用来保存链表的长度
    LNode *p=L;             //p为工作指针
    while(p->next!=NULL){   //计算链表的长度
        p=p->next;
        n++;
    }
    p->next=L;              //循环执行完后，p指向链表尾结点
                            //将链表连成一个环
    for(int i=1;i<=n-k;i++) //寻找链表的第n−k个结点
        p=p->next;
    L=p->next;              //令L指向新链表尾结点的下一个结点
    p->next=NULL;           //将环断开
    return L;
}


3）本算法的时间复杂度为O(n)，空间复杂度为O(1)。

15. 单链表有环，是指单链表的最后一个结点的指针指向了链表中的某个结点（通常单链表的最后一个结点的指针域是空的）。试编写算法判断单链表是否存在环。 1）给出算法的基本设计思想。 2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。 3）说明你所设计算法的时间复杂度和空间复杂度。

2）
LNode* FindLoopStart (LNode *head){
    LNode *fast=head, *slow=head;    //设置快慢两个指针
    while (fast!=NULL && fast->next!=NULL){
        slow=slow->next;             //每次走一步
        fast=fast->next->next;       //每次走两步
        if (slow==fast) break;       //相遇
    }
    if (fast==NULL||fast->next==NULL)//没有环，返回NULL
        return NULL;
    LNode *p1=head, *p2=slow ;       //分别指向开始点、相遇点
    while (p1!=p2){
        p1=p1->next;
        p2=p2->next;
    }
    return p1;                       //返回入口点
}

3）当fast与slow相遇时，slow肯定没有遍历完链表，故算法的时间复杂度为O(n)，空间复杂度为O(1)。

16. 设有一个长度n(n为偶数)的不带头结点的单链表，且结点值都大于0，设计算法求这个单链表的最大孪生和。孪生和定义为一个结点值与其孪生结点值之和，对于第i个结点（从0开始），其孪生结点为第n−i−1个结点。要求： 1）给出算法的基本设计思想。 2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。 3）说明你的算法的时间复杂度和空间复杂度。

2）本题代码如下：
int PairSum(LinkList L) {
    LNode *fast=L->next,*slow=L;//利用快慢双指针找到链表的中间点
    while(fast!=NULL&&fast->next!=NULL){
        fast=fast->next->next;  //快指针每次走两步
        slow=slow->next;        //慢指针每次走一步
    }
    LNode *newHead=NULL,*p=slow->next,*tmp;
                                //反转链表后半部分的元素，采用头插法
    while(p!=NULL){
        tmp=p->next;            //p指向当前待插入结点，令tmp指向其下一结点
        p->next=newHead;        //将p所指结点插入到新链表的首结点之前
        newHead=p;              //newHead指向刚才新插入的结点，作为新的首结点
        p=tmp;                  //当前待处理结点变为下一结点
    }
    int mx=0; p=L;
    LNode *q=newHead;
    while(q!=NULL){             //用p和q分别遍历两个链表
        if (p->data+q->data>mx) //用mx记录最大值
            mx=p->data+q->data;
        p=p->next;
        q=q->next;
    }
    return mx;
}

3）本算法的时间复杂度为O(n)，空间复杂度为O(1)。

17.

3）
typedef int ElemType;        //链表数据的类型定义
typedef struct LNode{        //链表结点的结构定义
    ElemType data;           //结点数据
    struct LNode *link;      //结点链接指针
}LNode, *LinkList;

int Search_k(LinkList list,int k){
    LNode *p=list->link,*q=list->link; //指针p、q指示第一个结点
    int count=0;
    while(p!=NULL){                    //遍历链表直到最后一个结点
        if (count<k) count++;          //计数，若count<k只移动p
        else q=q->link;                //之后让p、q同步移动
        p=p->link;
    }
    if(count<k)
        return 0;                      //查找失败返回0
    else {                             //否则打印并返回1
        printf("%d",q->data);
        return 1;
    }
}

18.

2）
typedef struct Node{
    char data;
    struct Node *next;
}SNode;

/*求链表长度的函数*/
int listlen(SNode *head) {
    int len=0;
    while (head->next!=NULL){
        len++;
        head=head->next;
    }
    return len;
}

/*找出共同后缀的起始地址*/
SNode* find_list(SNode *str1,SNode *str2) {
    int m, n;
    SNode *p,*q;
    m=listlen(str1);        //求str1的长度，O(m)
    n=listlen(str2);        //求str2的长度，O(n)
    for(p=str1;m>n;m--)     //若m≥n，使p指向链表中的第m-n+1个结点
        p=p->next;
    for(q=str2;m<n;n--)     //若m<n，使q指向链表中的第n-m+1个结点
        q=q->next;
    while(q->next!=NULL&&p->next!=q->next) //查找共同后缀起始点
        p=p->next;          //两个指针同步向后移动
        q=q->next;
    return p->next;         //返回共同后缀的起始地址
}

19.

2）
typedef struct node {
    int data;
    struct node *link;
}NODE;
Typedef NODE *PNODE;

3）
void func (PNODE h,int n) {
    PNODE p=h, r;
    int *q;
    q=(int *)malloc(sizeof(int)*(n+1)); //申请n+1个位置的辅助空间
    for(int i=0;i<n+1;i++)               //数组元素初值置0
        *(q+i)=0;
    while (p->link!=NULL) {
        m=*(q+m)=0? p->link->data:-p->link->data; //判断该结点的data
        if (*(q+m)==0) {                          //首次出现
            *(q+m)=1;                             //标记为已出现
            p=p->link;                            //保留该结点
        }
        else{                                     //重复出现
            r=p->link;                            //删除该结点
            p->link=r->link;
            free(r);
        }
    }
    free(q);
}

20.

2）
void change_list(NODE*h){
    NODE *p,*q,*r,*s;
    p=q=h;
    while(q->next!=NULL){        //寻找中间结点
        p=p->next;               //p走一步
        q=q->next;
        if(q->next!=NULL) q=q->next; //q走两步
    }
    q=p->next;                   //p所指结点为中间结点，q为后半段链表的首结点
    p->next=NULL;
    while(q!=NULL){              //将链表后半段逆置
        r=q->next;
        q->next=p->next;
        p->next=q;
        q=r;
    }
    s=h->next;                   //s指向前半段的第一个数据结点，即插入点
    q=p->next;                   //q指向后半段的第一个数据结点
    p->next=NULL;
    while(q!=NULL){              //将链表后半段的结点插入到指定位置
        r=q->next;               //r指向后半段的下一个结点
        q->next=s->next;         //将q所指结点插入到s所指结点之后
        s->next=q;
        s=q->next;               //s指向前半段的下一个插入点
        q=r;
    }
}