526互联

代码随想录算法训练营第四天| 24. 两两交换链表中的节点, 19.删除链表的倒数第N个结点，面试题02.07.链表相交，142.环形链表Ⅱ

发布时间 2023-09-10 10:12:33作者: zz子木zz

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

mydemo（超时）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        
        ListNode* dummy = new ListNode();
        dummy->next = head;
        ListNode* cur = dummy;
        ListNode* tmp1 = cur->next;
        ListNode* tmp2;
        ListNode* tmp3;

        if(tmp1 != NULL)
        {
            tmp2 = tmp1->next;
            if(tmp2 != NULL)
                tmp3 = tmp2->next;
            else
                tmp3 = NULL;
        }
        else
        {
            tmp2 = NULL;
            tmp3 = NULL;
        }

        while(cur->next != NULL || cur->next->next != NULL)
        {
            tmp2->next = tmp1;
            tmp1->next = tmp3;
            cur->next = tmp2;
            cur = tmp2;
        }

        return dummy->next;
    }
};

mydemo2

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        
        ListNode* dummy = new ListNode();
        dummy->next = head;
        ListNode* cur = dummy;
        ListNode* tmp;
        
        while(cur->next != NULL || cur->next->next != NULL)
        {
            tmp = cur->next;
            cur->next = cur->next->next;
            
            tmp->next = cur->next->next;
            
            cur->next->next = tmp;
            
            cur = cur->next;
        }

        return dummy->next;
    }
};

报错，tmp->next = cur->next->next;这一行报了空指针错误

Line 25: Char 36: runtime error: member access within null pointer of type 'ListNode' (solution.cpp)

两个错误

//while(cur->next != NULL || cur->next->next != NULL)
while(cur->next != NULL && cur->next->next != NULL)

tmp = cur->next;
cur->next = cur->next->next;
            
tmp->next = cur->next->next;
            
cur->next->next = tmp;
            
//cur = cur->next;
cur = cur->next->next;

关于指针的一点思考

指向 = 地址

ListNode* curl = new ListNode(0);
ListNode* head = new ListNode(1);
curl->next = head;

此时,curl->相当于指向，head相当于地址

直观来看，就是改变箭头指向的终点

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

mydemo 暴力法

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        
        ListNode* dummy = new ListNode();
        dummy->next = head;
        ListNode* cur = dummy;
        int len = 0;
        int i = 0;

        while(cur->next)
        {
            cur = cur->next;
            len++;
        }

        cur = dummy;
        while(i<len-n)
        {
            cur = cur->next;
            i++;
        }

        ListNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;

        return dummy->next;
    }
};

双指针法

思路：要删倒数第N个元素，那就先让快指针走N步，再让快慢指针一起动，当快指针到达末尾时，满指针也就到达了要删除的地方

细节：为了删除节点，慢指针应当到达要删除节点的前一个节点处，所以快指针应当先走N+1步

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        
        ListNode* dummy = new ListNode();
        dummy->next = head;
        ListNode* fast = dummy;
        ListNode* slow = dummy;
        
        n++;
        while(n-- && fast!=NULL)    //fast!=NULL 防止空指针错误
        {
            fast = fast->next;
        }

        while(fast)
        {
            slow = slow->next;
            fast = fast->next;
        }
        if(slow->next!=NULL)    //防止空指针错误
        {
            ListNode* tmp = slow->next;
            slow->next = slow->next->next;
            delete tmp;
        }
        
        return dummy->next;
    }
};

面试题 02.07. 链表相交

mydemo 暴力遍历法——成功

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        
        ListNode* fast = headA;
        ListNode* slow;

        while(fast)
        {
            slow = headB;   //每次遍历之前，先回到起点
            while(slow)
            {
                if(fast == slow)    
                {
                    return fast;
                }
                slow = slow->next;
            }
            fast = fast->next;
        }

        return NULL;
    }
};

注意，在每次遍历前需要先回到起点

slow = headB;   //每次遍历之前，先回到起点

相减法——（代码随想录）

/**
 * 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) {
        
        if(headA==NULL || headB==NULL)  return NULL;

        int lenA = 0;
        int lenB = 0;
        ListNode* cura = headA;
        ListNode* curb = headB;

        //求A链表的长度
        while(cura != NULL)
        {
            cura = cura->next;
            lenA++;
        }        
        //求B链表的长度
        while(curb != NULL)
        {
            curb = curb->next;
            lenB++;
        }

        //找出长链和短链
        int lenMax = lenA > lenB? lenA : lenB;
        int lenMin = lenA <= lenB? lenA : lenB;
        ListNode* headMax = lenA > lenB? headA : headB;
        //ListNode* headMin = lenA < lenB? headA : headB;
        ListNode* headMin = lenA <= lenB? headA : headB;
        ListNode* curMax = headMax;
        ListNode* curMin = headMin;

        //移动curMax
        curMax = headMax;
        for(int i=0; i<lenMax-lenMin; i++)
            curMax = curMax->next;
        
        //找交叉点
        while(curMax != NULL)
        {
            if(curMax==curMin)  return curMax;
            curMax = curMax->next;
            curMin = curMin->next;
        }
        return NULL;
    }
};

一个隐藏的坑：

为什么不能写成注释里的样子？

ListNode* headMax = lenA > lenB? headA : headB;
//ListNode* headMin = lenA < lenB? headA : headB;
ListNode* headMin = lenA <= lenB? headA : headB;

考虑一种特殊情况：当lenA=lenB时，则headMax = headB, headMin = headB，两个都一样了。所以不能写成注释里的样子

不过，当要赋的值时常数则无所谓，相等就相等呗

int lenMax = lenA > lenB? lenA : lenB;
int lenMin = lenA < lenB? lenA : lenB;

但是为了安全起见，以后统一写成：

int lenMax = lenA > lenB? lenA : lenB;
int lenMin = lenA <= lenB? lenA : lenB;

142.环形链表Ⅱ

mydemo——（成功）

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

        //判断有无环，若有环则求出相遇点
        do{
            if(fast == NULL || fast->next == NULL)
                return NULL;
            else
            {
                fast = fast->next->next;
                slow = slow->next;
            }
        }
        while(fast != slow);

        //求出环的入口
        index2 = fast;
        while(index1 != index2)
        {
            index1 = index1->next;
            index2 = index2->next;
        }
        return index1;
    }
};

小心一个坑,do-while语句最后是有一个 ；的；

do{
    
}
while();

卡哥demo

思路一致，但是卡哥的写法更简洁

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

        while(fast != NULL && fast->next != NULL)
        {
            fast = fast->next->next;
            slow = slow->next;
            if(fast==slow)
            {
                ListNode* index = fast;
                while(head != index)
                {
                    head = head->next;
                    index = index->next;
                }
                return index;
            }
        }
        return NULL;
    }
};