「代码随想录算法训练营」第四天 | 链表 part2

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

题目链接:https://leetcode.cn/problems/swap-nodes-in-pairs/
题目难度:中等
文章讲解:https://programmercarl.com/0024.两两交换链表中的节点.html#算法公开课
视频讲解: https://www.bilibili.com/video/BV1YT411g7br
题目状态:有思路,但细节缺乏考虑

个人思路:

  1. 首先判断head和其下一节点是否是nullptr,若是,就直接返回head
  2. 创建两个指针firstsecond,再创建一个辅助指针tmp用于保存second的下一节点;
  3. 在循环中利用tmp指针,将firstsecond交换;
  4. 返回head

出现的问题:

  1. 循环的结束条件比较难以设置;
  2. 当返回head时,只是从交换后的链表的第二节点返回,需要再使用一个节点用来指向第一节点。

修改思路:

添加一个哨兵指针dummy指向head,并且改变辅助指针tmp的指向,指向first的前一节点。

最终代码:

/**
 * 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 dummy(0);
        dummy.next = head;
        ListNode *prev = &dummy;
        while(prev->next != nullptr && prev->next->next != nullptr) {
            ListNode *first = prev->next;
            ListNode *second = first->next;
            prev->next = second;
            first->next = second->next;
            second->next = first;
            prev = first;
        }
        return dummy.next;
    }
};

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

题目链接:https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
题目难度:中等
文章讲解:https://programmercarl.com/0019.删除链表的倒数第N个节点.html
视频讲解: https://www.bilibili.com/video/BV1vW4y1U7Gf
题目状态:通过,有思路,且细节把控方面比上题强

个人思路:

使用快慢指针进行遍历。

  1. 不管三七二十一,先创建一个哨兵指针dummy
  2. 初始化两个快慢指针:slowfast,指向dummy
  3. 先将fast向后遍历n步,之后fastslow指针一起向后遍历,直到fast->next == nullptr
  4. 当遍历完成后,slow->next就是我们要删除的节点,创建一个辅助指针tmp指向slow->next,将slow->next = slow->next->next,然后删除tmp
  5. 返回dummy.next

最终代码:

/**
 * 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(0);
        dummy.next = head;
        ListNode *fast = &dummy;
        ListNode *slow = &dummy;
        for(int i = 0; i < n; ++i) {
            fast = fast->next;
        }
        while(fast->next != nullptr) {
            fast = fast->next;
            slow = slow->next;
        }
        ListNode *tmp = slow->next;
        slow->next = slow->next->next;
        delete tmp;
        return dummy.next;
    }
};

面试题 02.07.链表相交

题目链接:https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/
题目难度:简单
文章讲解:https://programmercarl.com/面试题02.07.链表相交.html
题目状态:无法理解题目,看文章讲解勉强通过

纱布题,根本不说人话,看了文章讲解才看懂讲的什么意思,交点不是数值相同,而是指针相同

代码展示:

/**
 * 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 lenA = 0, lenB = 0;
        while(curA != nullptr) {
            lenA++;
            curA = curA->next;
        }
        while(curB != nullptr) {
            lenB++;
            curB = curB->next;
        }
        curA = headA;
        curB = headB;
        if(lenB > lenA) {
            swap(lenA, lenB);
            swap(curA, curB);
        }
        int gap = lenA - lenB;
        while(gap--) curA = curA->next;
        while(curA != nullptr) {
            if(curA == curB) return curA;
            curA = curA->next;
            curB = curB->next;
        }
        return nullptr;
    }
};

142. 环形链表 II

题目链接:https://leetcode.cn/problems/linked-list-cycle-ii/
题目难度:中等
文章讲解:https://programmercarl.com/0142.环形链表II.html
视频讲解: https://www.bilibili.com/video/BV1if4y1d7ob
题目状态:之前在《剑指Offer》中看到过这个题,还记得大致思路,但是实际编写代码的时候还是出现了一些问题,最终通过

思路:
总体上是使用两次快慢指针解决

  1. 首先判断其链表是不是环形的,采用快慢指针解决,当慢指针与快指针相遇时,表明该链表是环形的,返回相遇的节点;
  2. 利用相遇的节点继续向下遍历,当节点再一次与自己相等时,表明该节点围绕了环形一圈,由此获得环形的大小;
  3. 通过环形的大小,再次利用快慢指针从头节点遍历,当快指针和慢指针相等时,获得了环形链表的入口节点。

⚠️注意:
这两次快慢指针用法不同。

  1. 第一次使用的快慢指针中,快指针每次走两步,慢指针每次走一步;
  2. 第二次使用的快慢指针中,快指针先走一段,之后快慢指针按照相同的速度向后遍历。

具体代码:

/**
 * 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 *CycleNode = InCycle(head);

        if(CycleNode == nullptr) return nullptr;
        int CycleNum = 1;
        for(ListNode *n = CycleNode; n->next != CycleNode; n = n->next) {
            CycleNum++;
        }

        ListNode *fast = head;
        for(int i = 0; i < CycleNum; ++i) fast = fast->next;
        ListNode *slow = head;
        while(fast != slow) {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }

    ListNode *InCycle(ListNode *head) {
        if(head == nullptr || head->next == nullptr) return nullptr;
        ListNode *slow = head->next;
        ListNode *fast = slow->next;
        while(slow != nullptr && fast != nullptr && fast->next != nullptr) {
            if(slow == fast) return slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        return nullptr;
    }
};

链表总结(来自代码随想录):

热门相关:邪王追妻99次:娘子,等我   首席的强娶豪夺:离婚365次   亿万老公,送上门!   异界之极品奶爸   文娱缔造者