线性表的链式表示

1. 静态链表需要分配较大的连续空间，插入和删除不需要移动元素
2. 某线性表中最常见的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D）存储方式最节省时间。
   A 单链表 B 仅有头指针的单循环链表 C 双链表 D 仅有尾指针的单循环链表
   注意涉及到删除节点需要知道当前节点的前驱节点，一般是否使用双链表看是否有删除操作，是否是循环看对头尾节点的操作
3. 带头结点的双循环链表L为空的条件是（D）这里容易误选B

A L->prior == L && L->next == NULL
B L->prior == NULL && L->next == NULL
C L->prior == NULL && L->next == L
D L->prior == L && L->next == L

同理循环单链表判空条件不是头节点是否为NULL，而是头指针是否指向L

4. 设计一个递归算法，删除不带头结点的单链表L中所有值为x的结点
   思路:递归出口是L为空的时候；当前结点是x的时候需要进行删除，然后仍然从当前结点位置开始递归；如果当前结点不等于x则指向next继续进行递归

void delete(LinkList &L,Elemtype x){
   if(L==NULL)
    return;
   LNode* p;
   if(L->data == x)
   {
   p = L;
   L = L->next;//L代表当前链表的头指针，所以需要将下一个结点赋值给L，因为L始终是代表头节点的
   free(p);
   delete(L,x);   
}
  else{
  delete(L->next,x);
  }   
}  
}

5. 在带头结点的单链表L中，删除所有值为x的结点，并释放其空间，假设值为x的结点不唯一。
   思路一：遍历一遍，找到待删除结点直接删除
   思路二：使用尾插法（直接插入排序思想），将不等于x的结点插入到L的后面

//思路一
LinkList delete1(LinkList &L,int x){
 LNode * q=L;
 LNode * p=q->next;
 while(p!=NULL){//这里不能用p->next!=0这样的话p结点本身的data域并没有进行判断
 if(p->data == x)
 {
    q->next=p->next;
    p=q->next;
 }
 else
 {p=p->next;
 q=q->next;}
 //这里必须加else，否则每次都会执行一遍，应该是上面不成立这里才会执行
 }
 return L;
}
//思路二
LinkList delete2(LinkList &L,int x){
    LNode * p,* now;
    now = L->next;
    p = now;
    while(p!=nullptr){
    if(p->data != x）{
       now -> next = p;
       now = p;
       p = p->next;        
} 
 else//这里必须加else，否则如果是上面满足的话也会略过一个元素
   p = p->next; 
}
now -> next = nullptr;//结束的时候忘了把尾结点置空
return L;
}

6. 设L为带头结点的单链表，从头到尾反向输出所有值
   思路一：从头到尾遍历链表，将数据存储在栈中，最后读出的时候从栈顶读出即可
   思路二：先逆序然后再输出
   思路三：使用递归模拟思路一进行反序输出

//思路一
# define MaxSize 10000
void printAll1(LinkList &L){
  int stack[MaxSize];
  int top=0;
  LNode * p = L->next;
  while(p!=NULL){
  stack[top++]=p->data;
}
   for(int i=top-1;i>=0;i++)
   {
   print(stack[i]);
}
}
//思路二
void reverse(LinkList &L){
    if(L==nullptr)
      return;
    LNode * p = L;
    LNode * q = p->next;
    else{
    p->next = nullptr;
    q->next = p;
    reverse(L->next);
    }
}
void printAll2(LinkList &L){
    reverse(L);
    L = L->next;//有头节点
    while(L!=NULL)
       print(L->data);
}
//思路三
void printAll3(LinkList &L){
   LNode * p = L;
   if(L->next!=NULL)
   printAll3(L->next);
   print(L->data); 
}

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

LinkList delete(LinkList &L){
if(L ==nullptr)
  return nullptr;
LNode * minpre, *pre;//使用两个结点保存要删除的结点和其前驱结点
LNode * minp, * p;
minpre = pre = L->next;
minp = p = pre->next;
while(p!=nullptr){
if(minp->data > p->data)
{   
    minp = p;
    minpre = pre;
}
 p = p->next;
 pre = pre->next;
}
//执行删除
minpre->next = minp->next;
free(minp);
return L;
}

8. 编写算法将带头节点的单链表L就地逆置，即空间复杂度是O(1)
   思路一：采用头插法，将后面元素依次插入第一个元素后面
   思路二：设置三个指针分别指向当前元素，然后通过指针的变换将顺序颠倒，注意第一个结点next域置空，然后原来的最后一个结点前面应该添加一个头节点指向原来的尾结点。

//思路一
LinkList reverse1(LinkList &L){
LNode *p,*q;
p = L->next->next;
q = L->next;
q->next = nullptr;
while( p->next!=nullptr){
   L->next = p;
   p = p->next;
   L->next->next = q;
   q = L->next;
}
L->next = p;
p->next = q;
return L;
}
//思路二
LinkList reverse2(LinkList &L){
LNode * pre,*p,*next;
pre = L->next;
p = pre->next;
next = p->next;
pre->next = nullptr;
while(next!=nullptr){
p->next = pre;
pre = p;
p = next;
next = next->next;
}
L->next = p;
return L;
}

9. 有一个带头节点的单链表L，设计一个算法使其元素递增有序
   思路一：使用直接插入排序，将当前结点与前面已经排好序的结点进行比较，找到最佳位置，然后将当前结点插入
   思路二：先将数据复制到数组中，然后使用排序算法进行排序，最后再依次将元素插入到链表中 （空间换时间）

LinkList sort(LinkList &L){
  LNode * p = L->next ,* pre;
  LNode * r = p->next;
  p->next = nullptr;
  p = r;
  while(p!=nullptr){
  r = p->next;
  pre = L;
  while(pre->next!=nullptr&&pre->next->data < p->data){
    pre = pre->next;
}
   p->next = pre->next;
   pre->next = p;
   p = r;
}
}

10. 设在一个带表头结点的单链表中所有元素结点的数据值无序，试编写一个函数，删除表中所有介于给定两个值之间的元素的元素（若存在）

LinkList delete1(LinkList &L,int a,int b){
 LNode * q=L;
 LNode * p=q->next;
 while(p!=NULL){//这里不能用p->next!=0这样的话p结点本身的data域并没有进行判断
 if( p->data>a&& p->data<b )
 {
    q->next=p->next;
    p=q->next;
 }
 else
 {p=p->next;
 q=q->next;}
 //这里必须加else，否则每次都会执行一遍，应该是上面不成立这里才会执行
 }
 return L;
}

11. 给定两个单链表，编写算法找出两个链表的公共结点
    公共结点的特点（想到了)因为是单链表所以从第一个公共节点开始向后的所有结点都是公共的，不可能再出现分叉
    思路一：先将两个链表逆序，然后一对一的比较寻找（考虑到两个链表的长度可能不相等的，但是如果有公共结点的话，后面到前面是对齐的，所以考虑从后往前找，但是感觉不太好）
    思路二：暴力遍历O（len1*len2)
    思路三：分别遍历两个链表求得二者的长度，并求出二者之差。在长的链表上先遍历长度之差个结点之后，再同步遍历两个链表（从第一个公共结点到最后是重合的，所以二者必须是同时到达第一个公共节点的，先把长的那部分走出来）
    注意：这里的同步是解题意义上的同步

//如果有公共节点，返回从第一个公共节点开始的公共节点链表
LinkList find(LinkList &L1,LinkList &L2){
     int length1,length2;
     LNode *p1,*p2;//假设有头结点
     p1=L1->next;
     p2=L2->next;
     for(length1=0;p1!=nullptr;p1=p1->next,length1++);
     for(length2=0;p2!=nullptr;p2=p2->next,length2++);
     int distance = abs(length1-length2);
     if(length1>length2){
       // while(distance!=0){
       //  p1 = p1->next;
       //   distance--;
       //  这里可以简写
       while(distance--)
          p1 = p1->next;
        }
     }else{
        // while(distance!=0){
        //    p2 = p2->next;
        //    distance--;
       while(distance--)
          p2 = p2->next;
         }
     }
     while(p1!=nullptr){
     if(p1->data!=p2->data)
     {
        p1 = p1->next;
        p2 = p2->next;
     }
    else{
    return p1;
   }   
}
return nullptr;     
}

12. 给定一个带表头结点的单链表，设h为头指针，结点的结构为（data，next），data为整形元素，next为指针。试写出算法：按递增次序输出单链表中各结点的数据元素，并释放结点所在的存储空间（不允许使用数组作为辅助空间）
    思路一：使用直接插入排序，然后遍历输出，最后全部释放
    思路二：二重循环，每次都寻找出当前链表中最小的元素，然后输出并删除当前元素，抽重复操作直到链表为空，时间复杂度O（n^2)
    思路三：如果可以使用辅助空间，将链表中的数据全部复制到数组中，然后在数组中排序输出，将原来链表中元素全部删除（但是如果题意是要求输出一个删除一个的话，还需要按照数组中的顺序重新构建链表再删除），时间复杂度O（nlogn）

//思路二
void deleteMin(Linklist &head){
  LNode *pre,*p,*u;//pre是最小元素的前驱结点
while(head->next!=nullptr){   
    pre = head;
    p = pre->next;
    while(p->next!=nullptr)
{
    if(p->next->data<pre->next->data)
    {
       pre = p;
       p = p->next;
    }
}//找到最小的
    print(pre->next->data);
    u = pre -> next;
    pre->next = u->next;
    free(u);//删除最小结点
} //从头到尾遍历完成  
free(head);//释放头节点
}

13. 将一个带头结点的单链表A分解成两个带头节点的单链表A和B，使得A表中含有原表中序号为奇数的元素，而B表中含有原表中序号为偶数的元素，且保持相对顺序不变。
    思路：直接将第一个结点插入奇数表中，顺序第二个结点插入偶数表中

void divideA(Linklist &L,LinkList &A,LinkList &B){
      if(L == NULL&&L->next == nullptr)
         return;
      LNode *p=L->next;
      LNode *pA,*pB;
      A = (LinkList)malloc(sizeof(LNode));
      B = (LinkList)malloc(sizeof(LNode));
      A -> next = nullptr;
      B -> next = nullptr;
      pA = A;
      pB = B;
      while(p->next!=nullptr){
        pA -> next = p;
        pA = pA ->next;
        pB -> next = p->next;
        pB = pB ->next;
        p = p->next->next;
}         
      pA->next = p;
      pA->next->next = nullptr;
      pB->next = p->next;   
      
}

14. 设C={a1,b1,a2,b2,…,an,bn}为线性表，采用带头结点的hc单链表存放，设计一个就地算法，将其拆分为两个线性表，使得A={a1,a2,…,an},B={bn,bn-1,…,b1}
    思路：A数组使用尾插法，B使用头插法（因为B的顺序是反序）。注意使用头插法，需要保存插入元素的后继结点避免断链

void divide(LinkList &L,LinkList &L1,LinkList &L2){
     if(L == NULL&&L->next == nullptr)
         return;
      LNode *p=A->next,*q;
      LNode *ra = A;
      LNode *pA,*pB;
      A = (LinkList)malloc(sizeof(LNode));
      B = (LinkList)malloc(sizeof(LNode));
      A -> next = nullptr;
      B -> next = nullptr;
      pA = A;
      pB = B;
      while(p!=nullptr)
      {
        ra->next = p;
        ra = p;
        p=p->next;
        q=q->next;
        p->next = B->next;
        B->next = p;
        p=q;
        }
        ra->next =nullptr;
    }    
}

头插法一般要保存后继结点，尾插法一般保存前驱结点。

15. 在一个递增有序的线性表中，有数值相同的元素存在，若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素
    思路一：直接遍历找到相同的起始位置，找到相同的终止位置，然后只保留一个直接将中间的相同链部分丢弃
    思路二：使用尾插法，将头节点找下，从第一结点开始，依次与已经插入结点的最后一个元素比较，不等直接删除，相等删除更新到下一个

//过于简单，略

16. 假设有两个按元素数值递增次序排列的线性表，均以单链表的形式存储，请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表中的结点存放归并后的单链表
    思路：直接使用头插法，注意考虑可能有一个链表有剩余元素直接插入

//两个线性表中的元素按照
LinkList merge(LinkList &L1,LinkList &L2)
{
   LNode *p1,*p2,*q1,*q2;//q代表每个节点的后继节点，防止断链
   p1 = L1->next;
   p2 = L2->next;
   q1 = p1->next;
   q2 = p2->next;
   LinkList L = (LinkList)malloc(sizeof(LNode));
   L->next = NULL;
   LNode *p,*q;
   p = p1->data<p2->data? p1:p2;
   L->next = p;
   p = q->next;
   q = q->next;
   while(p1!=nullptr&&p2!=nullptr){
      if(p1->data < p2->data){
        p1->next = L->next;
        L->next = p1;
        p1 = q1;
        q1 = q1->next;
}
else{
        p2->next = L->next;
        L->next = p2;
        p2 = q2;
        q2 = q2->next;

}
}
 p = p1==nullptr? p2:p1;
q = p->next;
while(p){
   p->next = L-next;
   L->next = p;
   p = q;
   q = q->next;
}
return L;
}
//上面写的太麻烦了
void MergeList(LinkList &La,LinkList &Lb){
   LNode *r,*pa=La->next,*pb=Lb->next;
   La->next = NULL;//利用原来链表中的两个节点的意思是全部都要用原来的，选择的时候也得选择La和Lb中的一个
   while(pa&&pb){
   //根本不用考虑第一个节点后面没有元素所以真正的第一个节点需要进特殊处理，因为直街在La上执行就可以直接在La后卖接上相关节点
    if(pa->data<=pb->data){
      r = pa->next;
      pa->next = La->next;
      La->next = pa;
      pa = r;
}else{
      r = pb->next;
      pb->next = La->next;
      La->next = pb;
      pb = r;
}
}
//这里前面先进行一个判断，用一个已知但是后面不再使用或者未知重新设置的变量进行代替，这样后面就不用分支再写了。
 if(pa)
 pb = pa;
 while(pb){
   r = pb->next;
   pb->next =La->next;
   La->next = pb;
   pb = r;
   
}  
free(Lb);
} 

17. 设A和B是两个单链表（带头节点），其中元素递增有序。设计一个算法从A和B中公共元素产生单链表C，要求不破坏A、B的结点
    思路：因为链表的元素是递增有序的，所以可以直接将两个链表相对位置进行比较，较小的那个向前移动，较大的那个不动，直到比较到两个元素相等，创建一个等于两个节点值的新节点，再使用尾插法插入

//非递增，没有利用到递增有序
void merge1(LinkList &A,LinkList &B)
{
    LinkList C = (LinkList)malloc(sizeof(LNode));
    C->next = nullptr;
    LNode *pa = A->next,*pb = B->next,*pc = C;
    while(pa){
        while (pb) {
            if(pa->data == pb->data)
            {
                LNode *c = (LinkList)malloc(sizeof(LNode));
                c -> data = pa->data;
                c -> next = nullptr;
                pc ->next = c;
                pc = pc->next;
            }
            pb = pb->next;
        }
        pa = pa->next;
    }
}
//利用递增有序
LinkList merge2(LinkList &A,LinkList &B){
    LinkList C = (LinkList)malloc(sizeof(LNode));
       C->next = nullptr;
       LNode *pa = A->next,*pb = B->next,*pc = C;
    while(pa&&pb){
        while(pa->data < pb->data){
            pa = pa->next;
        }
        while(pa->data > pb->data){
            pb = pb->next;
        }
//        if(pa->data < pb->data){
//                   pa = pa->next;
//               }
//        if(pa->data > pb->data){
//                   pb = pb->next;
//               }
//            这里也可以每次只迭代一个值使用if不用while循环，但是感觉while会更快因为不用进行后面的判断，比较集中
        if(pa->data == pb->data){
            LNode *c = (LinkList)malloc(sizeof(LNode));
            c -> data = pa->data;
            c -> next = nullptr;
            pc ->next = c;
            pc = pc->next;
            pa = pa->next;
            pb = pb->next;
        }
    }
    return C;
}

18. 已知两个链表A和B分别代表两个集合，其元素递增排列，编制函数求A与B的交集，并存放于A链表中
    思路：设置两个工作指针pa和pb，因为两个表的元素递增排列，对两个表进行归并操作，只有同时出现在两个表中才连接到结果表中且只保留一个(这里是针对la和lb两个相等的来说只保留一个，不存在3个相同的，因为集合具有互异性），其他节点全部释放，当一个链表释放完毕，将另一个全部释放

LinkList union_form(LinkList &A,LinkList &B){
    LNode *pa = A->next,*pb = B->next;
    LNode *p = pa;
    LNode *preA = A,*preB = B;
    while(pa&&pb){
        if(pa->data<pb->data)
            //删除当前节点
        {
            LNode * temp = pa;
            preA->next = pa->next;
            free(temp);
            preA = preA ->next;
            pa = preA->next;
    
        }
        if(pa->data>pb->data){
            LNode * temp = pb;
            preB->next = pb->next;
            free(temp);
            preB = preB ->next;
            pb = preB->next;
        }
        else{
            LNode * next = pa->next;
            p->next = pa;
            pa -> next = p->next->next;
            preA->next = next;
            pa = next;
            LNode * temp = pb;
            preB -> next = pb->next;
            free(temp);
            pb = preB -> next;
            
        }
    }
    while(pa){
        LNode * u = pa;
        pa = pa->next;
        free(u);
}
    while(pb){
        LNode * u = pb;
        pb = pb->next;
        free(u);
    }
    pa -> next =nullptr;
    free(B)
    
    return A;
}

这里可以换一种写法，使用LNode设而不是LinkList是为了分清节点定义的时候代表的不同含义，以免使用的时候混淆。这里虽然使用原链表A进行操作，也可以使用一个新的变量代表A，这样的话在使用的时候思路更清晰

void merge(LinkList &la ,LinkList &lb){
    LNode* pa = la->next;
    LNode* pb = lb->next;
    LinkList pc = la;//这里使用pc作为交集的代表
    while(pa&&pb){
        if(pa->data==pb->data){
            pc->next = pa;
            pc = pa;
            pa = pa->next;
            LNode * u = pb;
            pb = pb->next;
            free(u);
        }
        else if(pa->data < pb->data){
            LNode* u = pa;
            pa = pa->next;
            free(u);
        }
        else {
            LNode* u = pb;
            pb = pb->next;
            free(u);
        }
    }
     while(pa){
            LNode * u = pa;
            pa = pa->next;
            free(u);
    }
        while(pb){
            LNode * u = pb;
            pb = pb->next;
            free(u);
        }
        pc->next = nullptr;
        free(lb);
       
}

19. 两个整数序列A=a1,a2,a3,…,am和B=b1,b2,b3,…,bn已经存入两个单链表中，设计一个算法，判断序列B是否是序列A的连续子序列
    思路：这个就是字符串匹配算法还可以用暴力解

//暴力就是从第一个开始与序列B进行比对，如果中间出现不相等的地方，B序列从开头重新开始，A序列下移一个单位

20. 设计一个算法用于判断带头结点的循环双链表是否对称
    思路：（prior, data, next)，设置两个指针分别指向头节点和尾结点，然后每次移动相同的步长，直到两个指针相遇或者相邻（相邻的也相等），则证明该循环双链表对称，在中间失败则返回0

int Sum(LinkList &L){
    LNode *p = L->next,*q = L->prior;
    while(p!=q&&p->next!=q){
        if(p->data!=q->data)
            return 0;
        else{
            p = p->next;
            q = q->prior;
        }
    }
    return 1;
}

21. 有两个循环单链表，链表头指针分别为h1和h2，编写一个函数将链表h2链接到链表h1之后，要求链接后的链表仍保持循环单链表的形式
    思路：很简单就是一个链表的连接，如果有头节点的话，b的头节点要去掉，然后A之前的尾结点指向末尾，B的尾结点指向A的链表头指针

LinkList Link(LinkList &h1,LinkList & h2){
    LNode * p,*q;
    p = h1;
    while(p->next!=h1){
        p = p->next;
    }
    q = h2;
    while(p->next!=h2){
        q=q->next;
    }
    p->next = h2;
    q->next = h1;
    return h1;
}

22. 设有一个带头节点的循环的单链表，其结点值均为正整数，设计一个算法，反复找出单链表中结点值最小的结点并输出，然后将该节点从中删除，直到单链表空为止，再删除表头结点
    思路：这基本上就直接告诉思路了，从头节点开始走到指向头节点的节点为止，找到最小的之后执行删除，直到整个链表被删空。

void find_min(LinkList &L){
    LNode *p,*pre,*minp,*minpre;
    while(L->next!=L){
        p = L->next;
        pre = L;
        minp = p;
        minpre = pre;
        while(p!=L){
            if(p->data <minp->data){
                minp = p;
                minpre = pre;
            }
            pre = p;
            p = p->next;
        }
        cout<<minp->data<<"";
        minpre->next = minp->next;
        free(minp);
    }
    free(L);
}

23. 设头指针为L的带有表头结点的非循环双向链表，其每个结点中除有pred（前驱指针）和data（数据）和next（后继指针）域外，还有一个访问频度域freq。再链表被启用之前，其值初始化为0.每当在链表中进行一次Locate（L，x）运算时，令元素值为x的结点中freq域的值递增并使此链表中结点保持按访问频度非增的顺序排列，同时最近访问的结点排在频度访问相同的结点的前面，以便使频繁访问的结点总是靠近表头。编写Locate（L，x）函数，返回找到结点的地址。
    思路：（pred，data，freq，next）
    注意几个点：
    （1）进行双向链表处理的时候相关指针的处理要稍微复杂一些
    （2）存在与之前相等的则比较和前面所有相等的相当于一个关于freq的新的小数组重新排序
    前面完全理解错误
    （1）每次处理x，对x的freq进行+1处理，同时根据freq进行排序
    （2）实际上是进行头插法，将每次访问的节点首先按照freq的大小排序，如果大小相同，则当前处理的节点插到这个相同序列的首部

LNode* Locate(LinkList &L,int x){
    LNode* p = L->next,*pre=L;
    LNode *now;
    //考虑到链表可能本身为空的情况，在开头加上对于p的判断
    while(p&&p->data!=x){
        p = p->next;
        pre = pre->next;
    }
    //没有考虑链表本身可能为空的情况
    if(!p)
    {
    cout<<"Linklist is null,no element x in it!"<<endl;
    return nullptr;
   }
   p->freq++;
   
   /*找到当前结点应该插入位置*/
   now = L->next;
   while(now->next->freq != p->freq){
     now = now->next;
     }
   
    /*将当前结点x断下*/
   pre -> next  = p->next;

 /*将当前结点插入到找到的位置*/
  p->next = now->next;
  now -> next = p;
  return p;   
}

24. 已知一个带有表头结点的单链表，结点结构为（data，link），假设该链表只给出了头指针list，在不改变链表的前提下，设计一个尽可能高效的算法查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data域并返回1，否则返回0.
    思路：使用双指针p和q，开始的时候两个指针都指向链表的头结点，设置一个计数器count，移动其中一个指针p，每次移动一个位置count+1，当count=k时，两个指针p和q开始同时移动，当指针p移动到链表尾部的时候指针q指向的位置即为倒数第k个位置

int search(LinkList &list,int k){
    LNode* p=list->next,*q=list->next;
    int count = 0;
    while(p!=nullptr){
      if(count<k) count++;
      else q = q->next;
      p =p->next;
      }
      if(count<k)
      {
      return 0;
}else{
    cout<<q->data<<endl;
    return 1;
    }
}
}

}

25. 假定采用带头节点的单链表保存单词，当两个单词有相同后缀的时候，则可共享相同的的存储空间。设str1和str2分别指向阿亮二单词所在单链表的头节点，链表结点结构为（data，next），设计一个在时间上尽可能高效的算法，找出由str1和str2所致两个链表共同后缀的起始位置。
    思路：同样使用两步遍历找出两个数列的长度，有相同后缀到最后都一样，把两个链表长度的差求出来，长的那个先进行遍历，把距离差遍历完毕之后，再两两对应进行比较排序。

//上面有类似的，略

26. 用单链表保存m个整数，结点的结构为（data，link）且|data|<=n（n为正整数）设计一个时间复杂度尽可能高效的算法，对链表中data的绝对值相等的结点，仅保留第一次的结点而删除其余绝对值相等的结点。
    思路一：二重循环，先将第一个节点看成是standard，从第二个节点开始进行，如果后面有绝对值和前面相同的元素直接删除，然后以第二个元素为standard，从第三个节点重复操作，直到整个链表处理完毕
    思路二：使用辅助数组。==|data|<=n（n为正整数）==很明显是告诉可以使用一个最大是n+1的数组来存储对应的元素 。依次扫描链表

void func(LinkList &L,int n){
     LNode p = L,r;
     int *q,m;
     q = (int*)malloc(sizeof(int)*(n+1));
     for(int i=0;i<n+1;i++) q[i]=0;
     while(p->next!=nullptr){
        m = p->next->data>0? p->next->data:-p->next->data;//不空的时候看一下当前data的正负
        if(++q[m]==1){
           p = p->next;
        }else{
           r = p->next;//当前删除当前赋值
           p->next = r->next;
           free(r);
        }
       }
       free(q);     
}

❀27.一个长度为N的整型数组A[1…N]，给定整数X，设计一个时间复杂度不超过O(nlog₂n)的算法，查找出这个数组中所有两两之和等于X的整数对。
思路：先将数组按照从小到大排序（使用时间复杂度为O(nlog₂n)的算法），然后分别从小端和大端开始寻找如果两端加起来小于x，小端+，否则大端+直到两个之指针相遇。

总结

1. 对于链表，常用的方法有头插法、尾插法、逆置法、归并法、双指针法等
2. 熟悉各类题型的思考角度和最佳思路，对具体问题要灵活变通
3. 对于顺序表由于可以直接存储，经常结合排序和查找的几种算法设计思路进行设计，如归并排序、二分查找等

最后

以上就是体贴寒风为你收集整理的数据结构（一）线性表练习题2线性表的链式表示的全部内容，希望文章能够帮你解决数据结构（一）线性表练习题2线性表的链式表示所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。