题目要求
LeetCode24两两交换链表中的节点
LeetCode19删除链表的倒数第N个结点
LeetCode面试题02.07链表相交
LeetCode142环形链表II
题目思路
24两两交换链表中的节点
本题采用具有虚拟头结点的链表来写，卡哥的示意图如下：
首先要交换的两个链表的前一个结点，然后修改指针，注意指针修改顺序，在修改的时候要时刻注意所修改的指针的后继能不能找到，如果修改之后找不到并且后续操作还需要用到这个后继，那就要把这个后继记录下来，带有虚拟头结点循环结束的条件是cur->next或cur->next->next==NULL,cur不可能为NULL，因为cur每次指向的是交换后的两个节点的第二个。
本题的源代码如下
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode *vhead=new ListNode(0);
vhead->next=head;
ListNode *cur=vhead;
while(cur->next!=NULL&&cur->next->next!=NULL)
{
ListNode *temp1=cur->next;
cur->next=cur->next->next;
ListNode *temp2=cur->next->next;
cur->next->next=temp1;
cur->next->next->next=temp2;
cur=cur->next->next;
}
return vhead->next;
}
};
19删除链表的倒数第n个结点
我拿到这道题的本能反应还是暴力破解，思路是，通过一次循环记录下一共有多少结点，再经过一次循环找到倒数第n个结点的前驱结点，然后进行删除操作
BUT！！！
这题还可以使用双指针法，思路是设置一个快指针和一个慢指针，快指针比慢指针要快n+1步，这样当快指针指向NULL的时候，慢指针正好指向倒数第n个结点的前驱。
双指针法是真的很妙，回想这个为什么可以用双指针法，以及之前做过的题，我发现，这种可以找到快慢指针关系的，用双指针法再合适不过了，只是这层关系比较难想，就比如我第一反应不会想到，快指针最终指向NULL这个关系。
注意：本题代码实现让快指针先多走一步，然后再用n的关系进行while循环，实现多走n+1步的目的，这个多走一步最好放到循环前，因为如果n太大，快指针可能循环后为空，本题源代码如下：
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode *vhead=new ListNode(0,head);
ListNode *slow=vhead;
ListNode *qucik=slow->next;
//不要把多走一步的操作放到slow后面，因为快指针可能为空
while(n&&qucik!=NULL)
{
qucik=qucik->next;
n--;
}
while(qucik!=NULL)
{
slow=slow->next;
qucik=qucik->next;
}
ListNode *temp=slow->next;
slow->next=slow->next->next;
delete temp;
return vhead->next;
}
};
面试题02.07 链表相交
拿到这题我的第一反应仍然是暴力破解，第二反应是，把链表逆置过来，从后往前检查，我当时还觉得自己贼聪明，终于想到了一个不是暴力破解的方法，结果实践起来写了很多代码，然而，由于太复杂并且不断改变链表结构，最后也没写出来！
这题卡哥的思路是，首先计算两个链表的长度，num=长的-短的，让长的从num开始，与短的逐一比对，当两个指针相等的时候，就返回这个指针，即为两个链表相交的结点。
这里要特别注意，链表相交不代表数值相同。本题源代码如下：
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int i=0,j=0;
ListNode *curA=headA;
ListNode *curB=headB;
while(curA!=NULL)
{
i++;
curA=curA->next;
}
while(curB!=NULL)
{
j++;
curB=curB->next;
}
curA=headA;
curB=headB;
//让A是比较长的那个
if(i<j)
{
swap(i,j);
swap(curA,curB);
}
int num=i-j;
//往后挪动num步
while(num--)
curA=curA->next;
while(curA!=curB&&curA!=NULL)
{
curA=curA->next;
curB=curB->next;
}
//这里不用再分情况讨论，如果没有相交的结点，返回curA也是返回NULL
return curA;
}
142环形链表II
这题给人一种要长脑子的感觉……推导很复杂，我也有点讲不明白，还是看代码随想录环形链表
lass Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *slow=head;
ListNode *quick=head;
int i=0;
//要判断空链表
if(head==NULL)
return NULL;
while(quick->next!=nullptr&&quick->next->next!=nullptr)
{
quick=quick->next->next;
slow=slow->next;
i++;
if(slow==quick)
break;
}
if(quick->next==nullptr||quick->next->next==nullptr)
return NULL;
else
{
quick=head;
{
while(slow!=quick)
{
slow=slow->next;
quick=quick->next;
}
return slow;
}
}
}
};
总结反思
我觉得可能需要在写算法题的时候想想为什么可以这样想，以后遇到哪种情况也可以这样想.
总归是坚持下来了，也总归是有一点点暴力破解之外的想法了，尽管想法还是有点复杂，加油加油，会越来越好的！