算法经典题二（链表）

算法经典题二（链表）

预备知识
链表
每个结点组成 数据域+指针域
相关操作：
1.插入结点
2.删除结点
3.判断是否为空
4.查找指定元素的值

例1-a 链表逆序（easy）
描述：已知链表头节点指针head,将链表逆序（不可申请额外空间）
分析：单链表只能单向访问，从头节点依次通过指针访问到后续节点。遍历访问节点，每访问到一个节点，就将其逆置。
操作：
1.建立新的头指针new_head
2.遍历节点，逆置每一个节点
a.备份head->next
b.修改head->next
c.移动new_head与head

例1-b 链表逆序2（medium）
描述：已知链表头节点指针head,将链表从位置m到n逆序（不可申请额外空间）
1<=m<=n<=链表长度
分析：寻找关键节点，逆置段头节点的前驱，逆置前头节点，逆置前尾节点，逆置端尾节点的后继

操作：
1.找到开始逆置的节点，记录该节点前驱，该节点，将head向前移动m-1个位置

2从head开始，逆置change_len = n-m-1个节点
3.将pre_head与new_head连接，modify_list_tail与head连接
实现：

例2 链表求交点（easy）
描述：已知链表A的头节点指针headA,链表B的头节点指针headB,两个链表相交，求两个链表交点对应的节点
题目要求：
1.如果两个链表没有交点，返回null
2.在求交点的过程中，不可以破坏链表的结构或者修改链表的数据域
3.可以确保传入的链表A与链表B没有任何环
4.实现算法尽可能使时间复杂度O（n）,空间复杂度O(1)

分析：交点，那么就是两个节点的第一个相同指针域
法一：使用set集合（里面的元素唯一）
操作：
1.遍历链表A，将A中的节点对应的指针（地址），插入set
2.遍历链表B，将B中的节点对应的指针（地址），在set中查找，发现的set中的第一个节点的地址，即为两个链表的交点。
代码实现：
法二：
操作：
1.计算headA链表长度，计算HeadB链表长度，较长的链表多出的长度
2.将较长链表的指针移动到和较短链表指针对齐的位置
3.headA与HeadB同时移动，当两个指针指向同一个节点时，即找到。

实现代码：

例3 链表求环（easy）
描述：已知链表中可能存在环，若有环返回环起始节点，否则返回null
分析：环起始节点的指针（地址）出现了两次

法一：使用set求环起始节点
操作：
1.遍历链表，将链表中的节点对应的指针（地址），掺入set
2.在遍历时，插入节点前，在set中查找，第一个在set中发现的节点的地址，就是链表环的起点
实现代码

法二：快慢指针赛跑
形象理解：（唤醒赛道）长跑时跑的快的人在多跑一圈后又遇到了跑的慢的人
快指针一次走两步，慢指针一次走一步

操作：
1.遍历列表，设置快慢指针
2.得到相遇的meet节点
3.从head与ment同时遍历，指针速度一致，相遇点即为环的起点

代码实现：

例4 链表划分（medium）
描述：已知链表头指针head与数值x,将所有小于或等于x的的节点放在大于或等于x的节点前，且保持这些节点原来的相对位置
分析：巧用临时头节点
操作：
1.建立两个临时头节点，及对应的指针
2.遍历链表，若原宿大于x,将其插入到大于x值的的临时头节点之后，否则插入到小于值的临时头节点之后
3.将两个链表拼接

例5 复杂链表的深度拷贝（hard）
必备知识（STL Map的使用）
描述：已知一个复杂的链表，节点中有一个指向本链表任意某个节点的随机指针（也可以为空），求这个链表的深度拷贝
分析：节点地址与节点序号对应
需要使用两个Map
代码实现：

例6-a 2个排序链表的合并（easy）
描述：已知两个已排序链表头节点指针l1与l2,将这两个链表合并，合并仍为有序链表，返回合并后的头节点

分析：比较l1和l2指向的节点，将较小的节点插入到pre指针后，向前移动较小节点对应的指针
操作：
1.遍历链表，比较两个链表的的，插入较小的
2.判断链表是否有剩余，将剩余部分插入到排序链表之后

例6-b K个排序链表的归并（hard）
描述：已知K个已排序链表头节点指针，将这K个链表合并，合并仍为有序链表，返回合并后的头节点

法一：暴力合并，沿用上一题的思想
时间复杂度极高

法二：排序后相连
分析：将节点放到vector中，再将vector排序，再将节点顺序相连


法三：分治后相连

总结：
后面几道题比较复杂，没想太清楚，需要
多复习研究。对c++语法不熟，有比较大的语言障碍。