算法刷题记录（day5）

LC160.相交链表

题目描述：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == nullptr || headB == nullptr) {
            return nullptr;
        }

        ListNode* pa = headA;
        ListNode* pb = headB;

        while (pa != pb) {
            pa = pa == nullptr ? headB : pa->next;
            pb = pb == nullptr ? headA : pb->next;
        }

        return pa;
    }
};

LC206.反转链表

题目描述：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
       ListNode* pre = nullptr;
       ListNode* cur = head;
       
       while (cur != nullptr) {
            ListNode* temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
       }

       return pre;
    }
};

LC234.回文链表

题目描述 ：给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

解题思路：可以将链表分为两段，找到链表前半段的结尾位置，反转后半段链表，最后通过遍历两个链表并进行比较得出结果，最后将链表复原。

class Solution {
public:
    //找到前半段的结尾节点
    ListNode* find1(ListNode* head) {
        ListNode* slow = head, * fast = head;

        while (fast->next != nullptr && fast->next->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
        }

        return slow;
    }

    //反转后半段链表 并返回反转后的起始节点
    ListNode* find2(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;

        while (cur != nullptr) {
            ListNode* temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }

        return pre;
    }

    bool isPalindrome(ListNode* head) {
        if (head == nullptr) return true;

        ListNode* FirstEnd = find1(head);
        ListNode* SecondStart = find2(FirstEnd->next);

        //用来遍历比较
        ListNode* left = head;
        ListNode* right = SecondStart;

        //bool res = true;    //用来标记
        while (left && right) {
            if (left->val != right->val) {
                return false;
            }

            left = left->next;
            right = right->next;
        }

        //复原链表
        FirstEnd->next = find2(SecondStart);

        return true;
    }
};

LC141.环形链表

题目描述：给你一个链表的头节点 head ，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 ，则返回 true 。 否则，返回 false 。

解题思路：使用快慢指针即可。

class Solution {
public:
    bool hasCycle(ListNode *head) {
       ListNode* fast = head;
       ListNode* slow = head;

       while (fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;

            if (slow == fast) return true;
       }

       return false;
    }
};

LC142.环形链表 II

题目描述：给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。

解题思路：与LC141类似，首先利用快慢指针找到slow == fast的位置，再设置两个指针分别指向头节点与当前slow节点，进行遍历，最后当两指针所指位置相同时，返回结果。本题与数学问题中的追及问题类似，在草稿纸上演算一下更为清晰。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;

        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;

            if (slow == fast) {
                ListNode* index1 = slow;
                ListNode* index2 = head;
                while (index1 != index2) {
                    index1 = index1->next;
                    index2 = index2->next;
                }

                return index1;
            }
        }

        return nullptr;
    }
};