12、单链表的删除和u0026考研真题实战

本章需要掌握：

1、单链表删除i位置元素？
2、看考研真题，背一下？
3、考研真题2019

1、删除元素

//删除第i个位置的元素
//删除时L是不会变的，所以不需要加引用
bool ListDelete(LinkList L,int i)
{
    LinkList p= GetElem(L,i-1);//拿到要删除结点的前一个结点
    if(NULL==p)
    {
        return false;
    }
    LinkList q=p->next;//拿到要删除的结点指针
    if(NULL==q)//当链表只有5个结点，删除第6个结点，出现这种异常情况时，避免程序崩溃
    {
        return false;
    }
    p->next=q->next;//断链
    free(q);//释放被删除结点的空间
    return true;
}

2、考研真题2019

【2019统考真题】设线性表L=（a1，a2，a3…an-2，an-1，an）采用带头结点的单链表保存，请设计一个空间复杂度为O(1)且时间上尽可能高效的算法，重新排列L中的各结点，得到线性表L’=(a1，an，a2，an-1，a3,an-2…)。

思路：找到链表中间结点，后链表逆置，合并两链表。

1、找出链表L的中间结点，设置p和q两个指针，指针p每走一步，q走两步，当q指向尾结点，p恰好指向中间节点。

2、然后L的后半段实现原地逆置。

3、从单链表前后两段中一次各取一个节点，按要求排序。

2.1我的代码

void change_list(NODE* h){
  NODE *p,*q,*r,*S;
  p=q=h;
  
  #1、找到中间结点,p指针移动一次,q指针移动两次
  whlie(q->next!=NULL){
    p = p->next;
    q = q->next;
    if (q->next!=NULL) q = q->next;
  }
  
  #2、链表逆置,头插法直接实现
  q = p->next;
  p->next = NULL;
  while(q!=NULL){
    r = q->next;
    q->next = p->next;
    p->next = q;
    q=r;
  }
  
  #3、排序
  s = h->next;
  q = p->next;
  p->next = NULL;
  while(q!=NULL){
    r = q->next;
    q->next = s->next;
    s->next = q;
    s = q->next;
    q = r;
  }
  
  
}

2.2王道代码

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
typedef struct LNode{
    ElemType data;//数据域
    struct LNode *next;
}LNode,*LinkList;

//找链表中间结点，并设置好L2链表
void find_middle(LinkList L,LinkList &L2)
{
    L2=(LinkList)malloc(sizeof(LNode));//第二条链表的头结点
    LinkList pcur,ppre;//双指针遍历，是考研初试常考的
    ppre=pcur=L->next;
    while(pcur)
    {
        pcur=pcur->next;
        if(NULL==pcur)//为了防止pcur为NULL
        {
            break;
        }
        pcur=pcur->next;
        if(NULL==pcur)//为了使得偶数个，ppre依然指向a1,a2,到a6中的a3结点
        {
            break;
        }
        ppre=ppre->next;
    }
    L2->next=ppre->next;//由L2头结点指向后面一半链表
    ppre->next=NULL;//前一半链表的最后一个结点，next要为NULL
}

void reverse(LinkList L2)
{
    LinkList r,s,t;
    r=L2->next;
    if(NULL==r)
    {
        return;//链表为空
    }
    s=r->next;
    if(NULL==s)
    {
        return;//链表只有1个结点
    }
    t=s->next;
    while(t)
    {
        s->next=r;//原地逆置
        r=s;//以下3句是3个指针同时往后走一步
        s=t;
        t=t->next;
    }
    s->next=r;
    L2->next->next=NULL;//逆置后，链表第一个结点的next要为NULL
    L2->next=s;//s是链表第一个结点，L2指向它
}

void merge(LinkList L,LinkList L2)
{
    LinkList pcur,p,q;
    pcur=L->next;//pcur始终指向组合后链表的链表尾
    p=pcur->next;//p用来遍历L1链表
    q=L2->next;//q指向L2第一个结点，q用来遍历L2链表
    while(p!=NULL&&q!=NULL)
    {
        pcur->next=q;
        q=q->next;//指向下一个
        pcur=pcur->next;
        pcur->next=p;
        p=p->next;//指向下一个
        pcur=pcur->next;
    }
    //任何一个链表都可能剩余一个结点，放进来即可
    if(p!=NULL)
    {
        pcur->next=p;
    }
    if(q!=NULL)
    {
        pcur->next=q;
    }
}



//尾插法新建链表
void list_tail_insert(LNode* &L)
{
    L= (LinkList)malloc(sizeof(LNode));//申请头结点空间，头指针指向头结点
    L->next=NULL;
    ElemType x;
    scanf("%d",&x);
    LNode *s,*r=L;//s是用来指向申请的新结点，r始终指向链表尾部
    while(x!=9999)
    {
        s=(LinkList)malloc(sizeof(LNode));//为新结点申请空间
        s->data=x;
        r->next=s;//新结点给尾结点的next指针
        r=s;//r要指向新的尾部
        scanf("%d",&x);
    }
    r->next=NULL;//让尾结点的next为NULL
}

void print_list(LinkList L)
{
    L=L->next;
    while(L!=NULL)
    {
        printf("%3d",L->data);
        L=L->next;
    }
    printf("\n");
}

int main() {
    LinkList L;//链表头，是结构体指针类型
    list_tail_insert(L);//输入数据可以为1 2 3 4 5 6 9999
    print_list(L);//链表打印
    //寻找中间结点，并返回第二条链表
    LinkList L2=NULL;
    find_middle(L,L2);//只有一个结点时，L2中是没有结点的
    printf("--------------------------------\n");
    print_list(L);
    print_list(L2);
    printf("--------------------------------\n");
    reverse(L2);
    print_list(L2);
    printf("--------------------------------\n");
    merge(L, L2);
    free(L2);
    print_list(L);
    return 0;
}