【5.线性表-链式表示-王道课后算法题】

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

bool delteElement(LinkList &L, int x) {
    LNode *p = L->next;
    LNode *pre = L, *q;
    while (p != NULL) {
        if (p->data == x) {
            q=p;
            p=p->next;
            pre->next = p;
            free(q);
        } else {
            pre = p;
            p = p->next;
        }
    }
    return true;
}

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

bool deleteMin(Linklist &L) {
    LNode *p = L->next;
    int value = 9999999;
    LNode *pre = L, *min = L->next, *preMin = L;
    while (p != NULL) {
        if (p->data < value) {
            value=p->data;
            min = p;
            preMin = pre;
            p = p->next;
        } else {
            pre = p;
            p = p->next;
        }
    }
    preMin->next = min->next;
    free(min);
    return true;
}

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

//头插法
bool invertList(Linklist &L) {
    LNode *p = L->next, *q ;
    L->next = NULL;
    while (p != NULL) {
        //q指向p的下一个 防止断链
        q=p->next;
        //将p插入到头结点之后
        p->next=L->next;
        L->next=p;
        p=q;
    }
    return true;
}

3.1 反向断链的方式

//反向断链 1 2 3 4
bool invertList2(Linklist &L) {
    // 空链表或只有一个节点的链表不需要反转
    if (L == NULL || L->next == NULL) {
        return true;
    }
    LNode *p = L->next;
    LNode *pre;
    LNode *r ;
    L->next = nullptr;
    while (p != NULL) {
        r = p->next; // 先保存下一个节点
        p->next = pre; // 反转当前节点的 next 指针
        pre = p; // 移动 pre 到当前节点
        p = r; // 移动 p 到下一个节点
    }
    L->next = pre; // 将头节点的 next 指向新的头节点
    return true;
}

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

bool deleteBetween(Linklist &L, int x, int y) {
    if (x >= y) {
        return false;
    }
    if (L->next == nullptr) {
        return false;
    }
    LNode *p = L->next, *pre = L, *q;
    while (p != nullptr) {
        if (x <= p->data && p->data <= y) {
            q = p;
            p = p->next;
            pre->next = p;
            free(q);
        } else {
            pre = p;
            p = p->next;
        }
    }
    return true;
}

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

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

6. 设C={a1,b1,a2,b2,…,an,bn}为线性表，采用带头结点的单链表存放，设计一个就地算法，将其拆分为两个线性表，使得A{a1,a2,…,an},B={bn,…,b2,b1}。

bool splitList(Linklist &L, Linklist &L2) {
    //p指向首元结点 r是为指针
    LNode *p = L->next, *r = L, *q;
    L2 = (LNode *) malloc(sizeof(LNode));
    L2->next = NULL;
    int count = 1;
    while (p != NULL) {
        if (count % 2 != 0) {
            r->next = p;
            r = p;
            p = p->next;
        } else {
            q=p->next;
            p->next=L2->next;
            L2->next = p;
            p = q;
        }
        count++;
    }
    //第一个链表最后r尾指针指向NULL
    r->next = NULL;
    return true;
}

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

bool deleteRepeat(Linklist &L) {
    LNode *p = L->next,*q;
    //这里判断条件为p->next!=NULL是为了让q有意义
    while (p->next!=NULL){
        q=p->next;
        //如果相同就删除当前相同元素的后一个 直到没有相同为止
        if (p->data==q->data){
            p->next=q->next;
            free(q);
        }else{
            p=p->next;
        }
    }
    return true;
}