1. Toy模板网首页
  2. > Toy博客

day4_24交换链表节点_19删除节点_面链表相交_142环形链表II

7月前 作者：清影ssq 分类：Toy博客 阅读(34) 违法举报

这篇具有很好参考价值的文章主要介绍了day4_24交换链表节点_19删除节点_面链表相交_142环形链表II。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

24 交换链表节点

题目链接

方案一：自己的方案

奇偶节点，思路比代码随想录中的更直观一些，但是需要进行分类讨论，设置的辅助节点也多一些。

/**
 * 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) {
        // 空链表或者链表length = 1
        if(!head || !head->next)
            return head;
        // length >= 2
        // 设置虚拟头节点且保存交换后的头结点
        ListNode* dummyHead = new ListNode(0, head);
        // 设置pre和curr节点，其中pre是奇数节点，curr是pre下一个偶数节点
        ListNode* pre = head;
        ListNode* curr = pre->next;
        ListNode* tmp = dummyHead;
        // 返回的头结点 newhead
        head = curr;
        while(pre && pre->next){
            curr = pre->next;
            // 交换pre和curr节点
            pre->next = curr->next;
            curr->next = pre;
            tmp->next = curr;
            tmp = pre;
            pre = pre->next;
        }
        return head;
    }
};

方案二：代码随想录

直接上图：

day4_24交换链表节点_19删除节点_面链表相交_142环形链表II,leetcode,链表,数据结构,leetcode,c++

需要注意的是要保存1,2,3节点，因为在改变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* swapPairs(ListNode* head) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* curr = dummyHead;
        while(curr->next && curr->next->next){
            ListNode* tmp1 = curr->next;
            ListNode* tmp2 = tmp1->next;
            ListNode* tmp3 = tmp2->next;
            curr->next = tmp2;
            tmp2->next = tmp1;
            tmp1->next = tmp3;
            curr = tmp1;
        }
        return dummyHead->next;

    }
};

19删除链表倒数第n个节点

题目链接

  1. 方案一：两边扫描，第一遍得到链表长度length，倒数n==正数length-（n-1)
  2. 方案二：fast指针先于slow指针n步，fast到null时，slow是待删除节点 
/**
 * 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) {
        // 两次扫描
        // 第一次扫描得到链表长度lengthlength
        // 倒数n == 正数 length-（n-1)
        // 使用pre，curr删除节点
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* pre = dummyHead;
        ListNode* curr = head;
        int length = 0;
        while(curr){
            length += 1;
            curr = curr->next;
        }
        curr = head;
        // curr 的index [1, length]
        for(int index = 1; index < length - (n - 1); index++){
            pre = curr;
            curr = curr->next;
        }
        // 删除
        pre->next = curr->next;
        delete curr;
        curr = nullptr;
        return dummyHead->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) {
        // fast指针比slow指针先行n步
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* pre = dummyHead;
        ListNode* curr = pre->next;
        for(int count = 1; count < n; count++){
            curr = curr->next;
        }
        while(curr->next){
            pre = pre->next;
            curr = curr->next;
        }
        // 删除待删除节点
        ListNode* tmp = pre->next;
        pre->next = tmp->next;
        delete tmp;
        return dummyHead->next;

    }
};

面试题 链表相交

题目链接

  1. 方案一：双层for循环

  2. 方案二：O(n），直接上图：需要注意的是要考虑A，B哪个更长一些，可以通过swap讲currB指向更长的链表。

day4_24交换链表节点_19删除节点_面链表相交_142环形链表II,leetcode,链表,数据结构,leetcode,c++

/**
 * 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) {
        // 两层for循环
        ListNode* dummyHeadA = new ListNode(0, headA);
        ListNode* dummyHeadB = new ListNode(0, headB);
        for(ListNode* currA = dummyHeadA; currA->next; currA = currA->next){
            for(ListNode* currB = dummyHeadB; currB->next; currB = currB->next){
                if(currA->next == currB->next)
                    return currA->next;
            }
        }
        return NULL;
    }
};

/**
 * 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) {
        // 计算AB长度，末尾对齐
        int lengthA = 0;
        int lengthB = 0;
        ListNode* currA = headA;
        ListNode* currB = headB;
        for(; currA; currA = currA->next)
            lengthA += 1;
        for(; currB; currB = currB->next)
            lengthB += 1;
        currA = headA;
        currB = headB;
        // 交换，使得currA指向最短链表
        if(lengthA > lengthB){
            swap(lengthA, lengthB);
            swap(currA, currB);
        }
        // B向前移动lengthB-lengthA位置
        for(int offset = 0; offset < lengthB - lengthA; offset++){
            currB  = currB->next;
        }
        while(currA){
            if(currA == currB)
                return currA;
            else{
                currA = currA->next;
                currB = currB->next;
            }
        }
        return NULL;

    }
};

142环形链表II

题目链接

这题完全求助于Carl大佬（双层for循环会超出时间限制）, 神奇的思路，神奇的数学啊。文章来源地址https://www.toymoban.com/news/detail-598169.html

/**
 * 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) {
        // 快慢指针，同时从head出发，fast每次移动2位，slow每次移动1位
        // 若有环，则相遇
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
            if(fast == slow){
                ListNode* tmp1 = fast;
                ListNode* tmp2 = head;
                while(tmp1 != tmp2){
                    tmp1 = tmp1->next;
                    tmp2 = tmp2->next;
                }
                return tmp1;
            }
        }
        return NULL;
        
    }
};

到了这里，关于day4_24交换链表节点_19删除节点_面链表相交_142环形链表II的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包