第四天| 24. 两两交换链表中的节点、 19.删除链表的倒数第N个节点、 160.相交链表、 142.环形链表II_C/C++

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

思考：每次处理要涉及到三个结点：要交换的两个结点以及前驱结点。注意循环结束条件以及操作先后顺序

代码：

class solution {
public:
    listnode* swappairs(listnode* head) {
        if (head == nullptr || head->next == nullptr)       //链表长度为0或1不用处理直接返回
            return head;
        
        listnode* dummyhead = new listnode(0);      //虚拟头结点
        dummyhead->next = head;
        listnode* firstnode = dummyhead;        //两交换结点的前驱结点
        listnode* threenode;        //第二个交换的结点
        while (firstnode->next != nullptr && firstnode->next->next != nullptr) {
            threenode = firstnode->next->next;
            firstnode->next->next = threenode->next;
            threenode->next = firstnode->next;
            firstnode->next = threenode; 
            firstnode = threenode->next;        //向后处理
        }
        head = dummyhead->next;
        delete dummyhead;
        return head;
    }
};

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

题目链接：19 删除链表的倒数第n个节点

思考：双指针法。快指针先移动n步，接着快慢指针一起移动，直到快指针指向结点为链表尾部指针时慢指针指向目标结点的前驱结点，然后删除链表结点操作。

代码：

class solution {
public:
    listnode* removenthfromend(listnode* head, int n) {
        listnode* dummyhead = new listnode(0);//虚拟头结点
        dummyhead->next = head;
        listnode* slow = dummyhead;     //慢指针
        listnode* fast = dummyhead;     //快指针
        while (n--)     //快指针先移动n步
            fast = fast->next;

        //快慢指针同步移动，到慢指针指向目标结点前驱结点
        while (fast->next != nullptr) {     
            slow = slow->next;
            fast = fast->next;
        }

        listnode* tmp = slow->next;
        slow->next = tmp->next;
        delete tmp;
        return dummyhead->next;
    }
};

leetcode 160.相交链表

题目链接：160 相交链表

思考：注意到链表尾部部分相同，所以先让指向两链表的指针末尾对齐即让长的链表指针先移动一段，再两链表指针同时移动并比较

代码：

class solution {
public:
    //获取链表长度
    int getlength(listnode *head) {
        int size = 0;
        listnode* cur = head;
        while (cur != nullptr) {
            cur = cur->next;
            size++;
        }
        return size;
    }

    listnode *getintersectionnode(listnode *heada, listnode *headb) {
        listnode* cura = heada;
        listnode* curb = headb;
        int lena = getlength(heada);
        int lenb = getlength(headb);

        //让大的链表存放在a中
        if (lenb > lena) {
            swap(cura,curb);
            swap(lena,lenb);
        }
        
        //让a,b末尾对齐
        int gap = lena - lenb;
        while (gap--) 
            cura = cura->next;
        
        while (cura != nullptr) {
            if(cura == curb)
                return cura;
            
            cura = cura->next;
            curb = curb->next;
        }
        return nullptr;
    }
};

leetcode 142.环形链表ii

题目链接：142 环形链表ii

思考：双指针法

判断有无环：快指针每次移动两步，慢指针每次移动一步，则如何链表有环则快指针一定会追上慢指针
找环的入口：假设从头结点到环形入口节点的节点数为x。环形入口节点到 fast指针与slow指针相遇结点结点数为y。从相遇节点再到环形入口节点节点数为 z。

慢指针移动步数：x + y + k1 * (y + z)

快指针移动步数：x + y + k2 * (y + z)

又由上叙得公式：x + y + k2 * (y + z) = 2 * [ x + y + k1 * (y + z) ]

简化得：x = (n - 1) * (y + z) + z (n >= 1)

则从头结点出发一个指针，从相遇节点也出发一个指针，这两个指针每次只走一个结点，那么当这两个指针相遇的时候就是环形入口的结点

代码：

class solution {
public:
    listnode *detectcycle(listnode *head) {
        listnode* slow = head;
        listnode* fast = head;

        while (fast != nullptr && fast->next != nullptr) {
            //快指针移动两步，慢指针移动一步
            slow = slow->next;
            fast = fast->next->next;

            if (slow == fast) {     //快慢指针相遇
                //找入口
                listnode* tmp = head;
                while (tmp != slow) {
                    tmp = tmp->next;
                    slow = slow->next;
                }
                return slow;
            } 
        }
        return nullptr;     //快指针指向空说明无环
    }
};

链表专题的总结：