牛客算法–第六章
题目二
判断一个链表是否为回文结构
【题目】
给定一个链表的头节点 head，请判断该链表是否为回文结构。
例如：
1->2->1，返回 true。
1->2->2->1，返回 true。
15->6->15，返回 true。
1->2->3，返回 false。
【要求】
如果链表长度为 N，时间复杂度达到 O(N)，额外空间复杂度达到 O(1)
总结，这道链表题是来考指针的操作。实话说，其实面试时候的每道链表题都是用来考指针的操作。
先讲，麻烦的操作，面试的时候不推荐。
第一种：学过C++中的STL的话，应该知道，List容器，这里判断链表是否为回文结构，可以简单粗暴的。
List<int> list1,list2;
假设list1中存储的就是原来的链表。
那么，直接调用<algorithm>中的reverse算法
即reverse(list2.begin(),list2.end());
然后直接比较 list1==list2?就可以。
第二种：其实和第一种方法，本质是一样的，就是想要用到逆序，然后进行比较，谈到逆序，自然也可以用数据结构栈来实现。那么这样的话，就又可以有两种子方案，就是可以入栈整个链表，也可以入栈半个链表。
第三种就是面试的时候想要考查的操作链表指针的算法：
假设数据：
1->2->3->2->1->null
我们的目标是将其变为以下结构：
null
1->2->3<-2<-1
其中令链表中间结点mid->null，也就是3的位置。
那么，如何操作呢？
使用快慢指针，list1一次走一步，list2一次走两步。
等到list2走到链表尾的时候，list1正好走到链表的中间位置，也就是mid。然后就是将链表的后半段进行逆序。完成以上结构的变形。
关键点，就是需要记录mid，和last，也就是链表中间和末尾的位置。链表的问题都需要注意防止出现断裂的现象。
还有一个关键点就是变形完成之后的遍历终止条件
l=head,r=last;
while(l!=null && r!=null)
{
l=l.next;
r=r.next;
}
为什么终止条件是这样呢？因为涉及到链表的结构是奇回文还是偶回文。
假如数据结构是偶回文：
1->2->3->3->2->1->null；
那么最后变形生成的结构是：
null
1->2->3<-3<-2<-1
其中第一个3的位置指向null。所以，可以看到，最终变形完成的链表结构是左右不对称的，所以终止条件设成这样。
最后还需要注意的就是，还需要将操作之后的链表结构将其恢复原状。
题目三
复制含有随机指针节点的链表
【题目】
一种特殊的链表节点类描述如下：
public class Node {
public int value;
public Node next;
public Node rand;
public Node(int data) {
this.value = data;
}
}
Node 类中的 value 是节点值，next 指针和正常单链表中 next 指针的意义一样，都指向下一个节点，rand 指针是 Node
类中新增的指针，这个指针可能指向链表中的任意一个节点，也可能指向 null。
给定一个由 Node 节点类型组成的无环单链表的头节点 head，请实现一个函数完成这个链表中所有结构的复制，并返
回复制的新链表的头节点。例如：链表 1->2->3->null，假设 1 的 rand 指针指向 3，2 的 rand 指针指向 null，3
的 rand 指针指向 1。复制后的链表应该也是这种结构，比如，1->2->3->null，1 的 rand 指针指向 3，2 的 rand
指针指向 null，3 的 rand 指针指向 1，最后返回 1。
【要求】
时间复杂度为 O(N)，额外空间复杂度 O(1)
第一种解法，用一个额外空间map来存储原来链表的结点的拷贝。
key值对应原来链表的结点；value值对应新建链表的对应结点的拷贝结点。
然后将拷贝的结点设置next，生成拷贝链表，也根据对应的rand指针，生成拷贝结点的rand指针，最后返回拷贝链表的头指针，也就是map（head），也就是原来链表头指针在map中对应的拷贝结点。
代码如下：
public static Node copyListWithRand1(Node head )
{
HashMap<Node,Node> map = new HashMap<Node,Node>();
Node cur head;
while(cur != null)
{
map.put(cur,new Node(cur.value));
cur=cur.next;
}
cur = head;
while(cur != null)
{
map.get(cur).next = map.get(cur.next);
map.get(cur).rand = map.get(cur.rand);
cur = cur.next;
}
return map.get(head);
}
第二种方法，还是考查指针的操作。
举例数据：
1->2->3->4->5->null
对其进行处理：
1->1->2->2->3->3->4->4->5->5->null
相应的随机指针也就好找了，如果1->rand指向3,那么1’->rand肯定指向3’，怎么找呢？就是3’=3->next；那么1’->rand=1->rand->next；
最后的问题就是将这个链表最后分解为两个链表。
题目四
两个单链表相交的一系列问题
【题目】
在本题中，单链表可能有环，也可能无环。给定两个单链表的头节点 head1 和 head2，这两个链表可能相交，也可能不相交。请实现一个函数，如果两个链表相交，请返回相交的第一个节点；如果不相交，返回 null 即可。
【要求】
如果链表 1 的长度为 N，链表 2 的长度为 M，时间复杂度请达到 O(N+M)，额外空间复杂度请达到 O(1)。
首先，讲一下算法原型，如何判定一个单链表是否有环。
第一种，就是直接用map进行存储并判断。
如果一个node不在map里面，就将其push进去，；如果一个nodey已经在map中了，那么就是说明有环了。
第二种，就是用快慢指针的方法判断有没有环，并且得出环的位置。
设置s为慢指针，f为快指针,设置s=f=head;
然后s=s.next,s一次走一步，f=f.next.next，f一次走两步。
如果有环的话，那么s指针和f指针会最终相遇。
如果f==null了，s和f还没有相遇过，那么这个单链表就没环。
那么，如果得到环的入口位置呢？
同样的，当s<mark>f的时候，新建一个node指针a=head，从单链表头部出发，a=a.next,同时s=s.next。两个指针都是一次走一步。那么等到a</mark>s的时候，a和s的位置就是环的入口。
接下来，开始回归本题。本题是判断两个链表是否相交。
那么把这道题打碎，可以有下面的几种组合：
1.一个链表有环，一个链表无环；
2.两个链表都无环；
3.两个链表都有环。
接下来分别探讨：
1.一个链表有环，一个链表无环；
这种情况，第一次听的时候，可能会感觉很复杂，啃不动，但是，别忘了，本题玩的是单链表，所以，就基于这一点，这种情况一定不会产生相交的情况，直接返回null。
2.两个链表都无环；
这种情况，可能有两种情况，两个链表可能是互相“||”平行的结构，也可能是“丫”型结构。不可能是“X”型结构，原因同样是因为两个是单链表。
如果是“||”平行结构，那么两条链表没有相交位置，直接返回null即可。
第一种方法就是用map，从头开始遍历list1的时候，就将其node结点push进入。等到遍历完list1，就从头开始遍历list2，如果遇到node已经在map的情况，那么node结点就是相交的位置。
第二种方法就是不用哈希表，直接从头开始遍历list1，记录list1的长度num1，从头开始遍历list2，记录list2的长度num2；
然后记录下num2和num1的差值cha，然后先让长度大的链表先走cha的长度，然后list1和list2开始一步一步走，直到碰到相同的node结点，就是两条链表相交的位置。
什么原理呢？
举例：
1->2->3->5->5->5->5->5->null
9->6->7->4->5->5->5->5->5->null
注意，这里是为了好理解，但是相交的含义是指地址相同，不是值相同。
如上图所示，**如果相交，那么相交部分是一样长的。且相交的位置是后面的部分。**所以可以这样计算。
3.两个链表都有环。
这种情况，有3种模式：
也就是总结为3种类型：“66”型、“YO”结合型、“B站”型。
那么对这3种类型分别如何处理呢？
1.“66”型：
应该和“B站”型相比较的说，参见第三点。
2.“YO”结合型：
本质上，我们其实可以将其作为“Y”型的升级版。
那么如何处理呢？我们已经可以分别得出list1的入环结点位置node1和list2的入环结点位置node2，并且这种情况下node1==node2，两者是同一结点。
那么原来的“Y”型结构的结束条件是“==NULL”，那么现在的“YO”型结构的结束条件就是“<mark>node1”,可以用哈希表map，也可以用遍历，计算二者长度的方法，来找到相交的位置。
**那么，一个前提就是，怎么判断出事这种情况呢？很简单，两个链表的入环结点是同一个，也就是node1</mark>node2，就可以得出这种情况，接着就是上面所说的处理了。**
3.“B站”型：
我们已经可以分别得出list1的入环结点位置node1和list2的入环结点位置node2，那么现在开始，移动node1指针，直到（node1==node1），也就是让它在“B站”型的环里转一圈，如果在转的过程中遇到了node2结点，那么就是说，的确是“B站”型，否则的话，就说明是“66”型。
如果是“66”型，两个链表不相交，直接返回null；
如果是“B站”型，那么node1和node2都是相交位置，可以返回其中任意一个。
在编程的时候，非常需要注意的就是，走两步的时候需要，时时刻刻检查是否为null，也就是虽然是走两步，也要走一步就检查一遍是否为null。
京公网安备 11010502036488号