3-7（单链表的相关算法题）

今天还是继续刷单链表的相关算法题
1、链表分割：就是将一个链表的值按照小于x或者大于等于x排序，但不改变相对位置。如链表1-3-5-2-6-7-4.x==4
排序后的单链表应该为1-3-2-5-6-7-4；
思想：定义2个头结点lesshead,greathead,并且需要2个尾节点lesstail,greattail;这个方面需要注意一点就是头结点的定义不是和指针定义一样，节点的定义需要malloc申请，listnode lesshead=(listnode)malloc(sizeof(listnode));第二步需要定义一个cur指针指向需要分割的链表，并将其每个节点的元素值与x比较，小于x的用尾插法插到lesstail后面，别的插到greattail的后面。这里买呢然后再将lesstail->next=greathead->next; greattail->next=NULL;一定需要将greattail->next=NULL，因为greattail作为新排序的尾部。
2、链表的回文结构（对称结构）如1-2-3-2-1；1-2-2-1.这样都是回文结构，
思想：利用快慢指针，来将链表中间分割，在将后半部逆序，和前半部的值一一比较，如果一样，就为回文结构。
需要注意一点就是记得定义一个Prev指针，来指向中间指针的前一个，因为需要将中间指针的前一个置为空。
3、相交链表：找到2个链表相交的起始节点
思想：2个链表相交，也就是2个链表有个共同的节点，也就是tail地址一样。
第一步：遍历2个链表，求出其2个链表的长度la,lb。利用abs(la-lb)求出这2个链表的差值的绝对值，第二步将长的链表独自移动abs位，这样就可以保证其2个链表的长度一样，就可以一一比较2个链表的地址。为什么需要移动长链表到2个链表长度一样呢？答：因为相交说明2个链表有个共同节点，也就是2个链表都存储了其地址值，所以需要一一对比，
4、环形结构：判断一个链表是否有环：
思想：快慢指针思想，将快指针一次移动2个节点，慢指针一次移动一个节点，如果有环，快指针必定会在环里面与慢指针相遇，假设快慢指针相距x，每走一次距离会缩短1，终会出现x等于0，所以必定有环，至于快指针一次为什么走2个节点，因为走3个节点或者n个节点都有可能使其2个指针遇不到。

5、环形结构Ⅱ：输出一个环形的人口节点
思想：一：利用假设在某个节点相遇，则将该节点前面的作为一部分，后面的作为一部分，将前后2部分作为2个链表，然后利用相交可以求出其入口。
二：利用快慢指针，找到相遇节点，然后利用数学距离公式，可以求人口

更多相关文章

随机推荐