day21

【面试题 02.07. 链表相交】

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int listLength(ListNode *head) { //返回链表结点总个数
        ListNode *temp = head;
        int result = 0;
        while (temp != nullptr) { 
            result++;
            temp = temp->next;
        }
        return result;
    }
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int ALength = listLength(headA);
        int BLength = listLength(headB); 
        ListNode *shortList = ALength < BLength ? headA : headB;
        ListNode *longList = ALength >= BLength ? headA : headB;
        if(shortList == nullptr || longList == nullptr)
            return nullptr;
        int extraNode = ALength >= BLength ? (ALength - BLength) : (BLength - ALength) ;
        while (extraNode) {
            longList = longList->next;
            extraNode--;
        }

        while (shortList != nullptr) {
            if (shortList == longList) {
                return shortList;
            }
            shortList = shortList->next;
            longList = longList->next;
        }
        return nullptr;
    }
};

• 四十分钟好像，较慢，一开始没思路，双指针法中类似这种 fast先走 然后fast和slow一起走的题型我都想不到这个思路

• 有了提示思路后 代码有几个问题

  • 关于while循环 以下两段代码等价 即while是先判断循环条件逻辑值 再执行循环体 后进行循环条件中的运算

    while (extraNode) {
                longList = longList->next;
                extraNode--;
            }
    while (extraNode--) {
                longList = longList->next; 
            }
    
    

  • 此外关于while循环 注意与if循环的判断是有次数的去别的 前者在符合条件的情况下一直执行循环体 后者在符合条件的情况下只执行一次循环体

  • 主函数 最后return 是对边界特殊值等的处理语句 不能写成short->next 因为跳出循环时short==nullptr 那么之后就千万不能取值short->next 因为这等价于nullptr->next 这是不合法的 ！！！》》》》》换句话说，当你return时 需要留意可以return空 但不能return 某个对空的操作 会报错！！！老是错！！！

  • 另外关于return 没有考虑当最开始的头指针为空的情况 也就是链表本身为空 就直接返回空值 不需要再操作了！！！老是忘！！！

• 最总要的问题是 也是我花费时间最多的 是关于对未知谁是更大更长的两元素进行操作

  • 我的思路是： 找到谁长谁短并记下来：定义一个短链表指针 取比较语句中长度小的值 同理定义一个长链表指针 取比较语句中长度较长的值；定义一个表示两链表长度差值的整形变量 取比较语句中长度长的值-长度短的值的差；》》》》》最后遇到问题了 没考虑两链表长度相同的情况 所以在前面取值的时候 其中一个添加上等于号

    ListNode *shortList = ALength < BLength ? headA : headB;
    ListNode *longList = ALength >= BLength ? headA : headB;
    int extraNode = ALength >= BLength ? (ALength - BLength) : (BLength - ALength) ;
    
    	while (extraNode) {
                longList = longList->next;
                extraNode--;
    	}
    
    	while (shortList != nullptr) {
                if (shortList == longList) {
                    return shortList;
                }
                shortList = shortList->next;
                longList = longList->next;
    	}
    

  • 我之前的思路是：不管谁长谁短 两个while循环二选一移动指针就行

    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;
    }
    

  • 最好记得卡哥的思路：自己决定谁长谁短

    		// 让curA为最长链表的头，lenA为其长度
            if (lenB > lenA) {
                swap (lenA, lenB);
                swap (curA, curB);
            }
            // 求长度差
            int gap = lenA - lenB;
            // 让curA和curB在同一起点上（末尾位置对齐）
            while (gap--) {
                curA = curA->next;
            }
            // 遍历curA 和 curB，遇到相同则直接返回
            while (curA != NULL) {
                if (curA == curB) {
                    return curA;
                }
                curA = curA->next;
                curB = curB->next;
            }
    

  • 这部分还需要 再看看消化消化
    明天继续：）