Day4 链表剩下的基本操作

Lc24 
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

//画个图，弄个新节点，然后按照顺序进行连接，最主要的是连的时候思路要清晰
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyHead=new ListNode(0);
        dummyHead->next=head;
        ListNode* cur=dummyHead;
        while(cur->next!=nullptr&&cur->next->next!=nullptr){
            ListNode *temp1=cur->next;
            ListNode *temp2=cur->next->next->next;
            cur->next=cur->next->next;
            cur->next->next=temp1;
            cur->next->next->next=temp2;
            cur=cur->next->next;
        }
        return dummyHead->next;
    }
};

Lc19 删除链表倒数第n个元素，注意审题，一开始写成了显示倒数第n个元素，另外注意让快指针多走一步，这样方便慢指针直接删除元素。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *dummyNode=new ListNode(0);
        dummyNode->next=head; //每次自定义完记得让dummynode指向头节点
        ListNode *pre=dummyNode;
        ListNode *cur=dummyNode;
        while(n--&&cur!=NULL){
            cur=cur->next;
        }
        cur=cur->next;  //让快指针再多走一步，这样
        while(cur){
            cur=cur->next;
            pre=pre->next;
        }
        pre->next=pre->next->next;
        return dummyNode->next;
    }
};

///链表相交的题目，不知道为啥leetcode一直过不了，不理解。
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
      ListNode * curA= headA;
      ListNode * curB= headB;
      int lenA,lenB=0;//求一下两个链表的长度
      while(curA!=NULL){
          lenA++;
          curA=curA->next;
      }  
      while(curB!=NULL){
          lenB++;
          curB=curB->next;
      }
      curA=headA;
      curB=headB;
      if(lenB>lenA){
          swap(curA,curB);//保证永远是A最大
          swap(lenA,lenB);
      }
      int gap=lenA-lenB;
      while(gap--){
          curA=curA->next;
      }
      while(curA!=NULL){
          if(curA==curB){
              return curA;
          }
          curA=curA->next;
          curB=curB->next;
      }
      return NULL;
    }
};

环的进阶问题，实际上仔细思考很有意思 Lc142
首先是如何哦判断链表是否有环，这个很简单，就是快慢指针同时出发，如果相遇的话说明有环，如果没相遇的话说明无环。其次是判断环的相遇位置：这个就比较有意思了，直接让一个指针从当前位置出发，一个指针从头出发，他们第一次相遇的位置一定是环相遇的位置，也就是x=z

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast=head;
        ListNode *slow=head;
        while(fast!=NULL&&fast->next!=NULL){
            fast=fast->next->next;
            slow=slow->next;
            if(fast==slow){
                ListNode *index1=fast;
                ListNode *index2=head;
                while(index1!=index2){
                index1=index1->next;
                index2=index2->next;
                }
                return index2;
            }
          
        }
          return   NULL;
    }
};