代码随想录算法【Day4】

Day4

1.链表的题目，要在草稿纸上模拟清晰后就简单了

2.双指针更加灵活的应用。

3.环形链表多练习。

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

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* _dummyHead = new ListNode(0); //虚拟头结点
        _dummyHead -> next = head;
        ListNode* cur = head;
        ListNode* pre = _dummyHead;
        ListNode* tmp;
        while(cur != NULL && cur -> next != NULL){
            tmp = cur -> next -> next;
            //三个步骤
            pre -> next = cur -> next; 
            cur -> next -> next = cur;
            cur -> next = tmp;
            //更新值
            pre = cur;
            cur = tmp;
        }
        ListNode* result = _dummyHead->next;
        delete _dummyHead;
        return result;
    }
};

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

直接法：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        //直接法,需要两次遍历
        ListNode* _hummyHead = new ListNode(0); //虚拟头结点
        _hummyHead -> next = head;
        ListNode* tmp = nullptr, *cur = _hummyHead; 
        int count = 0; //记录节点个数
        if(cur -> next == NULL) return head;
        while(cur -> next != NULL){
            cur = cur -> next;
            count ++;
        }
        cur = _hummyHead;
        int m = count - n;
        //移动到要删除的节点的前一个位置
        while(m--){
            cur = cur -> next;
        }
        //删除操作
        if(cur -> next -> next != nullptr) 
                tmp = cur -> next ->next;
        delete cur -> next;
        cur -> next = tmp;
        return _hummyHead -> next;
    }
};

第一次写，没有加“if(cur -> next == NULL) return head;”这句，程序一直报错，在这里我debug了很久。

要注意，cur -> next为nullptr的话，cur -> next -> next 就是非法的。

双指针法

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        //快慢指针，只用遍历一遍就可以删除节点
        ListNode *_hummyHead = new ListNode(0);
        _hummyHead -> next = head;
        ListNode *slow = _hummyHead, *fast = _hummyHead;
        //先正常写，然后判断边界情况
        while (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 _hummyHead -> next;
    }
};

面试题 02.07. 链表相交

有点类似模拟题，思路清晰后挺简单的。

题目示例里面提到的，“题目条件如果两个链表相交则不能为 0”，意思是，0代表了NULL。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        //相交的节点指地址是相同的，值相同的节点不一定地址相同
        ListNode* curA = headA;
        ListNode* curB = headB;
        int lenA = 0, lenB =0;
        while(curA != NULL){
            lenA ++;
            curA = curA -> next;
        }
        while(curB != NULL){
            lenB ++;
            curB = curB -> next;
        }
        curA = headA;
        curB = headB;
        //让curA成为最长链表的头
        if(lenA < lenB){
            swap(lenA, lenB);
            swap(curA, curB);
        }
        int gap = lenA - lenB;
        //让两表对齐
        while(gap --){
            curA = curA -> next;
        }
        while(curA != curB && curA != nullptr){
            curA = curA -> next;
            curB = curB -> next;
        }
        return curA;
    }
};

142.环形链表II

1.如何判断链表有环？

快慢指针相遇

2.假如慢指针每次移动一步，快指针每次移动两步，会不会存在这样的一个情况，即快慢指针永远无法相遇？

可以这样来看，慢指针相对于快指针静止，快指针每次相对移动一步来遇到慢指针，所以不存在永远无法相遇的情况。

3.如何判断快慢指针一定会相遇？

假如快指针每次移动5步，慢指针每次移动2步，以3步为单位的相对移动。

本质上是看以3步为单位的移动，是否一定能遍历环上的所有节点

所以只有当环长L不是3的倍数时才能相遇

4.环的入口怎么找？

快慢指针的运动如下图所示：

假设快慢指针在环中的某一点相遇，设：

①slow = x + y

（而不是 slow = x+y+n(y+z)，因为慢指针被快指针追上的时候，慢指针一定在走第一圈)

②fast = x + y + n(y+z)

因为fast = 2 * slow

有等式： 2 * (x + y) = x + y + n(y +z)

得到：x = n(y + z) - y，整理得：③x = (n - 1)(y + z) + z，其中n ≥ 1

由③式可知，让慢指针1和慢指针2分别从起点和相遇点出发，他们总会在环的入口相遇，这样就找到了环的入口。

5.慢指针被快指针追上的时候，为什么一定是在慢指针走第一圈的时候？

假设快指针已经走了3圈，把环铺开，如下图，慢指针没转完一圈，一定就被快指针追上了。

以下是我ac的代码，做的多余判断太多了，建议去看一下网站上的代码。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        //判断是否有环
        //记得考虑一下只有一个节点的情况和没有节点的情况
        ListNode* slow = head, *fast = head;
        if(head == nullptr || head->next == NULL) return NULL;
        while(fast != nullptr && fast->next != NULL){
            slow = slow -> next;
            fast = fast -> next -> next;
            if(slow == fast) break;
        }
        if(fast == nullptr|| fast->next == NULL) return NULL;
        //如果有环，返回入环的第一个节点
        ListNode *cur = head;
        while(cur != slow){
            slow = slow -> next;
            cur = cur -> next;
        }
        return cur;
    }
};

以下是我第一次写的报错的代码，刚开始就让快指针走了两步，导致表达式发生变化，所以报错，代码一定要严格按照表达式来。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        //判断是否有环
        //特殊判断一下只有一个节点的情况和没有节点的情况
        if(head == NULL && head -> next == NULL) return NULL;
        ListNode* slow = head, *fast = head -> next -> next;
        while(fast != nullptr && slow != fast){
            slow = slow -> next;
            fast = fast -> next -> next;
        }
        if(fast == nullptr) return NULL;
        //如果有环，返回入环的第一个节点
        ListNode *cur = head;
        while(cur != slow){
            slow = slow -> next;
            cur = cur -> next;
        }
        return cur;
    }
};