学习线性表_3

单链表的删除

1. 直接删除即可
2. 删除后要free

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

练习

设线性表L=(a1,a2,a4,…,an),采用带头结点的单链表存储，设计一个空间复杂度为O(1)且时间上尽可能高效的算法，重新排列L中的各结点，得到线性表L=(a1,an,a2,an-1…)

分析：

1. 空间复杂度是O(1),我们不能申请额外的空间
2. 找到链表的中间结点，前面一半是链表 L
3. 将链表的后半部分给一个新的头结点 L2
4. 然后将链表 L2 进行原地逆置
5. 再将 L 和 L2 链表进行合并

问题一：如何找到链表的中间结点

1. 如果首先遍历一次链表,长度假如是20,再次遍历走到第10个,这样的缺点是遍历了两次链表。
2. 更好的办法：双指针法，两个指针同步向后遍历的方法。
3. 定义两个指针pcur,ppre，让pcur指针每次走两步,
   ppre指针每次走一步,这样当pcur指针走到最后,那么ppre指针刚好在中间。
4. 注意,由于pcur每次循环是走两步的,因此每走一步都注意判断是否为NULL。
5. 画图证明，无论奇数还是偶数，都可实现
6. 把前一个列表的元素放多1个更方便，但是其实哪个多都一样

问题二： 后一半链表设置为L2，如何让L2原地转置

1. 以上步骤循环往复，直到t为NULL时，结束循环
2. 这时s是最后一个结点,r是倒数第二个结点,需要再
   次执行一下s->next=r
3. 最后需要L2->next->next=NULL;因为原有链表的头结点变成链表最后一个结点, 最后一个结点的next需要为NULL,这时让L2指向s,因为s是原链表最后一个结点
4. 完成了逆置后,就是第一个结点,因此链表头结点L2指向s。

问题三：L和L2链表合并，轮流放结点

1. 因为空间复杂度是O(1)，不申请新空间，需要3个指针pcur,p,q
2. 合并后的新链表让 pcur指针始终指向新链表尾部，初始化为pcur=L->next，使用p指针始终指向链表L待放入的结点，初始化值为p=L2->next
3. q指针始终指向链表L2待放入的结点,初始化值为q=L2->next
4. 因为链表L的第一个结点不动，所以p=p->next
5. 开启循环，循环结束后，有可能L还剩余一个结点，也可能L2剩余一个结点,但是只会有一个剩余的有结点
6. 因此判断p不为NULL，把p放入,如果q不为NULL，把q放入即可。