前言：链表练习的第二天，对链表的理解加深了
24. 两两交换链表中的节点
这个题一开始的思路是用cur和next两个指针来做，但是绕来绕去绕迷糊了，最后超时了。把错误的代码放在下面警醒大家：
主要问题出现在这两行代码，next.next发生了更改。
next.next=next.next.next;
next.next.next=next;
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy=new ListNode(0,head);
ListNode cur=dummy;
ListNode next=head;
while(next!=null && next.next!=null){
cur.next=next.next;
next.next=next.next.next;
next.next.next=next;//这一步有问题因为next.next已经被更改了
cur=next;
next=next.next;
}
return dummy.next;
}
}
这个题还是3个指针清晰一些。代码如下：
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy=new ListNode(0,head);
ListNode cur=dummy;
while(cur.next!=null && cur.next.next!=null){
ListNode node1=cur.next;
ListNode node2=cur.next.next;
cur.next=node2;
node1.next=node2.next;
node2.next=node1;
cur=cur.next.next;
}
return dummy.next;
}
}
递归版本想不出来，看了一下答案写出来了。
该递归也是反向交换，先到达最后两个节点交换完回到上一层交换上两个节点。
代码如下：
class Solution {
public ListNode swapPairs(ListNode head) {
if(head==null || head.next==null){
return head;
}
ListNode next=head.next;
ListNode swapHead=swapPairs(next.next);
head.next=swapHead;
next.next=head;
return next;
}
}
总结：该递归的关键是理解最后一层head=null，达到边界条件，返回值swapHead=null，此时交换不需要指定swapHead下一个指向睡，只需要将head指向swapHead，next指向head即可。
19.删除链表的倒数第N个节点
思路：该题使用快慢指针来做，让fast先走n步，再一起往前走，当fast为null时，slow刚好指到要删除节点的前一个。
注意：slow删除节点时需要判断slow.next是否为null，避免空指针异常
代码如下：
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy=new ListNode(0,head);
ListNode fastNode=dummy;
ListNode slowNode=dummy;
for(int i=0;i<n+1;i++){
fastNode=fastNode.next;
}
while(fastNode!=null){
fastNode=fastNode.next;
slowNode=slowNode.next;
}
if(slowNode.next!=null){
slowNode.next=slowNode.next.next;
}
return dummy.next;
}
}
面试题 02.07. 链表相交
思路：链表A和链表B存在差值，首先先让长链表将指针移到差值的位置，使得链表AB的尾端对齐，再一起向前走知道两个指针指向同一位置。
代码入下：
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int lengthA=0,lengthB=0;
ListNode pointA=headA,pointB=headB;
while(pointA!=null){
pointA=pointA.next;
lengthA++;
}
while(pointB!=null){
pointB=pointB.next;
lengthB++;
}
pointA=headA;
pointB=headB;
int diff=0;
if(lengthA>lengthB){
diff=lengthA-lengthB;
for(int i=0;i<diff;i++){
pointA=pointA.next;
}
}else if(lengthA<lengthB){
diff=lengthB-lengthA;
for(int i=0;i<diff;i++){
pointB=pointB.next;
}
}
while(pointA!=pointB && pointA!=null){
pointA=pointA.next;
pointB=pointB.next;
}
return pointA;
}
}
合并链表的方法更加巧妙一些，其原理是如果将两个长度不同的链表连在一起长度就相同了，A+B和B+A长度相同且后端对齐，可直接遍历两个合并的链表，如果指针对应相等则为相交的点。
注意：不用考虑元素相不相同的问题，因为比较的是节点相不相同，即节点的地址是否一致。
代码如下：
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode point1=headA;
ListNode point2=headB;
while(point1!=point2){
if(point1==null){
point1=headB;
}else{
point1=point1.next;
}
if(point2==null){
point2=headA;
}else{
point2=point2.next;
}
}
return point1;
}
}
142.环形链表II
思路：这个题之前做过，用快慢指针。快指针每次走两步，慢指针每次走一步。搞清x（head到环开始的距离） y（环开始到相遇的距离） z（相遇到环结束的距离）以及走的步数m的关系是关键。最重要得到x和m的关系
假设 fast多走一圈与x相遇，由x+y+y+z=2（x+y）得x=z;
即使多圈后相遇，也可由x+y+n(y+z)=2（x+y）得x=z;
也就是说从相遇点和head同时出发，两个指针同时到达环开始的位置。
步骤如下：
1、先找到相遇点；
2、从相遇点和起点同时出发两个指针；
3、一起向前走并记录步数，相遇时即为环的位置。
代码如下：
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode p1=head,p2=head;
while(p1!=null && p1.next!=null){
p1=p1.next.next;
p2=p2.next;
if(p1==p2){
ListNode index1=p1;
ListNode index2=head;
while(index1!=index2){
index1=index1.next;
index2=index2.next;
}
return index1;
}
}
return null;
}
}