两两交换链表中的节点、删除链表倒数第N个结点、链表相交、环形链表

题目要求

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;
            }
        }

    }
};

总结反思

  我觉得可能需要在写算法题的时候想想为什么可以这样想，以后遇到哪种情况也可以这样想.
  总归是坚持下来了，也总归是有一点点暴力破解之外的想法了，尽管想法还是有点复杂，加油加油，会越来越好的！