day10

[面试题02.07.链表相交]

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *curA = headA;
        ListNode *curB = headB;
        int countA = 0;
        int countB = 0;
        if(curA == nullptr || curB == nullptr)
            return nullptr;
        while(curA->next != nullptr){
            curA = curA->next;
            countA++;
        }
        while(curB->next != nullptr){
            curB = curB->next;
            countB++;
        }
        curA = headA;
        curB = headB;
        while(countA -countB >0){
            curA = curA->next;
            countA--;

        }
        while(countB - countA >0){
            curB = curB->next;
            countB--;
        }
        while(curA != nullptr){
            if(curA == curB)
                return curA;
            curA = curA->next;
            curB = curB->next;
        } 
        return nullptr;
    }
};

• 其实我本来没有思路的 而且也错会了题意——题目要求返回相交结点的指针 是要求指向这两个节点的指针地址相同 并不是要求这两个节点内存储的val相同。
• 看了卡哥思路，我就想着——先把两个链表各自遍历一遍得到各自节点个数——然后把结点个数多的那条链表当前指针向后移 直到该长链表从当前指针所指位置到最后一个结点之间的节点总个数与那条短的相等——接着就是两条链表的当前指针一起往后移，只要当前指针所指向的位置不相同 也就是这两个指针不相等的话 那就一起向后移。
• 我其实运行了一遍后 有一个错误 就是因为我没考虑如果一开始所给的链表其一或两者都是空链的情况要返回nullptr 只考虑到了两者一起往后移但没有交点要返回nullptr
• 去看看卡哥写的过程 应该比我这个更简洁吧

while(countA -countB >0){
            curA = curA->next;
            countA--;

        }
        while(countB - countA >0){
            curB = curB->next;
            countB--;
        }  

// 让curA为最长链表的头，lenA为其长度
        if (lenB > lenA) {
            swap (lenA, lenB);
            swap (curA, curB);
        }
        // 求长度差
        int gap = lenA - lenB;
        // 让curA和curB在同一起点上（末尾位置对齐）
        while (gap--) {
            curA = curA->next;
        }

• 上述代码前者是我写的 后者是卡哥写的 该段代码目的是为了移动较长链表的当前指针 直至两条链表当前指针所指结点到最后一个节点这段长度相等。
• 面对两个变量大小不确定的情况下要进行相见操作 我的方法是分两种情况 对应两个while 卡哥思路是 利用swap函数保证A>B 那么两者之差就是A-B while(差--){} 即可

[0142.环形链表II]

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast = head;
        ListNode *slow = head;
        while (slow != nullptr){
            while(fast != nullptr){
                if(fast->next == slow->next)
                    return slow->next;
                fast = fast->next;
            }
            slow = slow->next;
            fast = slow;
        }
        return nullptr;
    }
};

• 上述只能通过个别案例 不能通过循环入口是下标为0的第一个结点的情况

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast = head;
        ListNode *slow = head;
        while (slow != nullptr){
            while(fast != nullptr){
                if(fast->next == slow)
                    return slow;
                fast = fast->next;
            }
            slow = slow->next;
            fast = slow;
        }
        return nullptr;
    }
};

• 改了之后 超出时间限制

• 还是看看卡哥思路吧

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast = head;
        ListNode *slow = head;
        while (slow != nullptr){
            if(fast == slow){
                ListNode *index1 = fast;
                ListNode *index2 = head;
                while(index1 != index2){
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index1;
            }
            fast = fast->next->next;
            slow = slow->next;
        }
        return nullptr;
    }
};

• 看了思路后 写得是挺顺畅的 就是结果不对>-<
• 我知道有两处代码不一样 一处是if判断语句中 还有一处是fast走两步 slow走一步 放在while开头还是结尾
• 我先改了第二处 第一处没变 结果错误 报错为指向了空指针

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast = head;
        ListNode *slow = head;
        while (fast != nullptr){
            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 index1;
            }
        }
        return nullptr;
    }
};

• 只改第一处 不改第二处 结果跟之前两处都不改一样 能运行 但是是错误的结果

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
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 index1;
            }
        }
        return nullptr;
    }
};

• 正确答案就是卡哥那样写法 见上
• 哦 因为fast一次走两步 所以要求fast != nullptr && fast->next != nullptr;这样 fast才能取fast->next->next;
• 至于为什么fast = fast->next->next; slow = slow->next;这两句要放在while循环的开头而不是结尾 那是因为这俩快慢指针要一开始就得走哇 你放while循环的结尾也行 但只有在while中包含的其他语句并不会受到这俩变量值的影响就可以 。 而本题r如果放在循环的结尾而不是开头 那么if判断语句符合 俩指针岂不是一开始就进去了 那就直接执行return index1语句了 且此时index1并没有进入if循环下的那个whille 循环 值仍是head头结点 所以怎么样 结果都不会变的

明天继续:)