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

TFTree 发布于 2022-11-21 426 次阅读


AI 摘要

Excerpt: This article gives the solutions of four related list problems, namely "24. Swap Nodes in Pairs", "19. Remove Nth Node From End of List", "Intersection of Two Linked Lists" and "142. Linked List Cycle II". For problem "24. Swap Nodes in Pairs" and "19. Remove Nth Node From End of List", the author provided his own solutions as well as the standard solutions. For "Intersection of Two Linked Lists" and "142. Linked List Cycle II", only the standard solutions are given. The strategies of the standard solutions include using the virtual head node and the two-pointers technique.

24. 两两交换链表中的节点 - 力扣(LeetCode)

思路:这道题一定要把握好交换的顺序,否则很容易成环导致无法出循环

我的AC代码

//时间复杂度O(n),空间复杂度O(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* swapPairs(ListNode* head) {
        if((head == nullptr) || (head->next == nullptr)) {
            return head;
        }
        ListNode* dummyHead = new ListNode(-1,head);
        ListNode* cur = dummyHead;
        while(cur != nullptr && cur->next != nullptr && cur->next->next != nullptr) {
            ListNode* tmp = cur->next->next;
            cur->next->next = tmp->next;
            tmp->next = cur->next;
            cur->next = tmp;
            cur = cur->next->next;
        }
        return dummyHead->next;
    }
};

我的答案和标准答案顺序上不太一样,但运行起来效果差不多,所以这题不是只有一种特定的顺序,只要逻辑通就可以

标准答案

//时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
        dummyHead->next = head; // 将虚拟头结点指向head,这样方面后面做删除操作
        ListNode* cur = dummyHead;
        while(cur->next != nullptr && cur->next->next != nullptr) {
            ListNode* tmp = cur->next; // 记录临时节点
            ListNode* tmp1 = cur->next->next->next; // 记录临时节点

            cur->next = cur->next->next;    // 步骤一
            cur->next->next = tmp;          // 步骤二
            cur->next->next->next = tmp1;   // 步骤三

            cur = cur->next->next; // cur移动两位,准备下一轮交换
        }
        return dummyHead->next;
    }
};

19. 删除链表的倒数第 N 个结点 - 力扣(LeetCode)

思路:我的思路是先算出整个链表的长度,然后减去n以此得到需要删掉的节点在正数时的序号,然后遍历一遍删掉就行了

我的AC代码

//时间复杂度O(n),空间复杂度O(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) {
        int cnt = 0;
        ListNode* cur = head;
        ListNode* dummyHead = new ListNode(-1,head);
        while(cur != nullptr) {
            cnt++;
            cur = cur->next;
        }
        cnt = cnt - n;
        cur = dummyHead;
        while(cnt--) {
            cur = cur->next;
        }
        cur->next = cur->next->next;
        return dummyHead->next;
    }
};

标准答案的思路是双指针:

如果要删除倒数第n个节点,让fast移动n步,然后让fast和slow同时移动,直到fast指向链表末尾。删掉slow所指向的节点就可以了

标准答案

//时间复杂度O(),空间复杂度O()
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* slow = dummyHead;
        ListNode* fast = dummyHead;
        while(n-- && fast != NULL) {
            fast = fast->next;
        }
        fast = fast->next; // fast再提前走一步,因为需要让slow指向删除节点的上一个节点
        while (fast != NULL) {
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next; 

        // ListNode *tmp = slow->next;  C++释放内存的逻辑
        // slow->next = tmp->next;
        // delete nth;

        return dummyHead->next;
    }
};

面试题 02.07. 链表相交 - 力扣(LeetCode)

思路:这道题主打的是题目描述很难理解,思路是先找出两个链表的长度,然后根据差值,设置两个指针,让这两个指针在同一起点出发,因为这题目判断的是链表相交,链表相交一个很重要的条件是相交的那个点的指针一定是相同的,这也是这题的易错点。起初我按照指针的值来判断,导致过不了样例。找到那个相交的指针以后,可以立即返回,因为后面一定是相同的(我自己的AC代码一直判断到结束,属于是画蛇添足了)

我的AC代码

//时间复杂度O(n+m),空间复杂度O(1)
/**
 * 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* a = headA;
        ListNode* b = headB;
        int indexa = 0;
        int indexb = 0;
        while(a != NULL) {
            ++indexa;
            a = a->next;
        }
        while(b != NULL) {
            ++indexb;
            b = b->next;
        }
        a = headA;
        b = headB;
        if(indexa > indexb) {
            int tmp = indexa - indexb;
            while(tmp--) {
                a = a->next;
            }
        }
        if(indexb > indexa) {
            int tmp = indexb - indexa;
            while(tmp--) {
                b = b->next;
            }
        }
        ListNode* slow = a;
        ListNode* fast1 = a;
        ListNode* fast2 = b;
        int flag = 0;
        while(fast1 != NULL) {
            if((fast1 == fast2)) {
                if(flag == 0) {
                    flag = 1;
                    slow = fast1;
                }
            }
            else {
                flag = 0;
                slow = NULL;
            }
            fast1 = fast1->next;
            fast2 = fast2->next;
        }
        return slow;
    }
};

标准答案

//时间复杂度O(n+m),空间复杂度O(1)
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* curA = headA;
        ListNode* curB = headB;
        int lenA = 0, lenB = 0;
        while (curA != NULL) { // 求链表A的长度
            lenA++;
            curA = curA->next;
        }
        while (curB != NULL) { // 求链表B的长度
            lenB++;
            curB = curB->next;
        }
        curA = headA;
        curB = headB;
        // 让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;
        }
        return NULL;
    }
};

142. 环形链表 II - 力扣(LeetCode)

思路:设置两个指针,快指针用来跑,慢指针用来记录环的入口,如果快指针跑的过程中遇到慢指针,那就说明有环,而且环的入口是慢指针。但是我不知道怎么从无限循环的状态中跑出来,只能设置一个cnt来记录,如果cnt > 1e4,那就说明已经跑完一圈了,那么肯定有环,而且慢指针不是入口,那慢指针就向后挪一位,如此反复就能得到答案了

推荐使用标准答案的快慢指针法

我的AC代码

/**
 * 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* dummyNode = new ListNode(-1,head);
        ListNode* slow = dummyNode;
        ListNode* fast = dummyNode;
        while(slow->next != NULL) {
            fast = slow->next;
            int cnt = 0;
            while(fast != NULL) {
                if(cnt > 1e4){
                    break;
                }
                if(fast == slow) {
                    return slow;
                }
                else {
                    fast = fast->next;
                }
                ++cnt;
            }
            slow = slow->next;
        }
        return NULL;
    }
};

标准答案

思路是先设置两个指针,指针slow每次移动一个节点,指针fast每次移动两个节点,这两个节点一定会相遇,在它们相遇的时候再设置两个指针,一个指针从头出发,一个指针从相遇的地方出发,这两个指针相遇的点就是入口,具体证明见代码随想录环形链表解析

/**
 * 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) {
            slow = slow->next;
            fast = fast->next->next;
            // 快慢指针相遇,此时从head 和 相遇点,同时查找直至相遇
            if (slow == fast) {
                ListNode* index1 = fast;
                ListNode* index2 = head;
                while (index1 != index2) {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index2; // 返回环的入口
            }
        }
        return NULL;
    }
};