24. 两两交换链表中的节点

https://leetcode.cn/problems/swap-nodes-in-pairs/

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head==NULL||head->next==NULL)return head;
        ListNode* tmp=new ListNode();
        tmp->next=head;
        tmp->val=head->next->val;
        ListNode* cur=head;
        ListNode* temp=NULL;//cur前面节点
        ListNode* right=head->next;//cur后面节点
        while(1){
            //交换
            if(right==NULL){//如果是三个的情况，第三个不交换直接返回
                break;
            }
            cur->next=right->next;
            right->next=cur;
            if(temp!=NULL)temp->next=right;
            if(cur->next==NULL)break;
            //更新
            temp=cur;
            cur=cur->next;
            right=cur->next;
        }
        
        return tmp;
    }
};

19.删除链表的倒数第N个节点

https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* cur=head;
        ListNode* newcur=head;
        int size=0;
        while(cur!=NULL){
            size++;
            cur=cur->next;
        }

        int l=size-n-1;//减一是为了跳到删除节点前面去
        if(l==-1){//删除第一个
            head=head->next;
            return head;
        }
        while(l--){
            newcur=newcur->next;
        }
        ListNode* temp=newcur->next;
        newcur->next=newcur->next->next;
        delete temp;
        return head;
    }
};

面试题 02.07. 链表相交

https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* temp=headB;
        ListNode* cura=headA;
        ListNode* curb=headB;
        while(cura!=nullptr){
            while(curb!=nullptr){
                if(cura==curb){
                    return curb;
                }
                curb=curb->next;
            }
            curb=headB;//注意从“头”开始
            cura=cura->next;
        }
        return NULL;
    }
};

142.环形链表II

https://leetcode.cn/problems/linked-list-cycle-ii/

利用双指针，一个快指针，一个慢指针，还有注意找数学关系（环形入口距离等于相遇离入口距离加上环形的n-1圈）

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* frontp=head;
                ListNode* endp=fast;
                while(frontp!=endp){
                    frontp=frontp->next;
                    endp=endp->next;
                }
                return frontp;
            }
        }
        return NULL;
    }
};

元旦快乐，新的一年快乐！！