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

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

题目链接：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 个结点，并且返回链表的头结点。

进阶：你能尝试使用一趟扫描实现吗？

思考：双指针法。快指针先移动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 相交链表

题干：给你两个单链表的头节点?headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

?

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

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

代码：

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

题干：给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

• ?为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。? ? ? ?
• 不允许修改给定的链表。

思考：双指针法

• 判断有无环：快指针每次移动两步，慢指针每次移动一步，则如何链表有环则快指针一定会追上慢指针
• 找环的入口：假设从头结点到环形入口节点 的节点数为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;     //快指针指向空说明无环
    }
};

链表专题的总结：

• 巧用虚拟头结点，简化单独处理的情况
• 熟练运用双指针，通过画图的方式来处理好具体步骤
• 画图算数理清思路，难题先在纸上明确公式，寻找破题关键