LeetCode每日一刷 --- 手撕单链表习题（2）
source link: https://blog.csdn.net/bit_zyx/article/details/123659504
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
目录
1、链表的回文结构
- 链接直达：
找中间节点再逆置，此法非常巧妙，找中间节点和逆置这两块内容在上一份博文中已经详细讲解过，这里不多赘述，这样做的原因是执行上述操作后遍历原头节点和逆置后新头节点，判断值是否相等，若遍历后都相等则返回true，反之false。
- 代码如下：
2、相交链表
- 链接直达：
法一：A链表的每个元素跟B链表依次比较，如果有相等，就是相交，第一个相等的就是交点。
此法的时间复杂度是O(M*N)，此法的优势就是在判断好是否相交后直接把相交的节点求出来了，注意：在比较的时候不能拿值去比较，要拿地址去比较。此法的缺陷就是效率相对较低，可以再进行改进。
法二：遍历原链表 + 快慢指针
先判断两个链表是否相交
依次遍历两个链表到尾，看两个尾节点地址是否相同，若相同则一定相交。此时的时间复杂度就是O(M+N)，相较于法一可是优化了太多。
再找出第一个交点
执行完上一步知道了链表相交，接下来就要求交点了，先求出两个链表的长度La，Lb。再定义连个指针分别指向两个链表的头，让长度较长的链表指针先走 | La-Lb | 步，再让两个链表指针一起走，若发现地址存在相同，那么就停止，此时找到交点。这种情况的时间复杂度同样是O(M+N)。
- 代码如下：
3、复制带随机指针的链表
- 链接直达：
法一：直接复制（malloc）+ 找相对距离
定义一个指针cur指向原链表第一个元素，cur指向第一个值为7，再malloc出一个7来，cur往后走，继续malloc，再尾插，以此遍历下去。新的链表复制出来了，关键在于如何处理新链表的random指针，这里可以采用找相对距离的方法，找原链表random指向第几个，那么新链表对应指向第几个。但是这个方法过于复杂，时间复杂度达到了O(N^2)。不是太推荐
法二：
首先，把拷贝节点链接在原节点后面
接着，链接拷贝节点的random在原节点random后面
比如我们拷贝出来的13这个数字，拷贝的13的random就是原头13的random的next 。因为在原链表中，13的random指向7，现在想让拷贝出来的13的random指向拷贝出来的7。原链表中，7的next指向拷贝出的7，综上：拷贝的13的random就是原头13的random的next 。以此类推。
最后，恢复原链表，把拷贝链表链接在一起
- 总代码如下：
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK