数据结构与算法--链表的应用
一、找到中间节点快指针走两步慢指针走一步快指针是空奇数或者快指针的p_next为空偶数停止此时的慢指针就是中间节点二、找到倒数第k个节点两个指针q先走k,然后p和q同时走直到q等于空p和q都要从p_head开始不能指向首节点三、判断链表是否有环用两个指针快指针和慢指针一开始都先指向头节点快指针走两步慢指针走一步当快指针等于慢指针说明找到环了。四、链表的逆序先判断传过来的头指针是不是有效的是不是传了空链表如果链表只有一个有效节点直接打印就行新建节点指向首节点头节点的指针域设置成空指针这样就把链表分为无头链表和空链表再用头插的方法把屋头链表插进空链表头插先插入的排后面。五、排序1.选择先判断传过来的头指针是不是有效的是不是传了空链表还有如果链表只有一个有效节点直接打印就行新建节点p_pos指向首节点用来记录位置新建节点p用来找数p从需要排序的位置的下一个节点开始找该位置的数比当前位置的数小就交换直到找到尾节点移动位置节点直到尾节点的前一个节点停止。2.冒泡用节点end记录每次需要比较到哪里新建节点next指向首节点next的值和next的next的值进行比较直到比较到倒数第二个节点不然next的next访问会段错误next会走到尾节点把这时候的next给end实现end前移直到end到首节点。3.插入首先分为排好序的部分和没排好序的部分第一个数默认排好了新建节点p_temp记录没排好序的部分也是准备要插入的节点再让首节点的指针域为空指针新建节点p_insert让p_insert从头开始找要插入的位置的前一个节点直到找到尾节点用next记录一下链表p_tmp后移用next找位置找到位置后插入节点直到p_temp全部插入。p_insert用来找位置p_temp要插入的节点next用来记录链表以防丢失
)
