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

2024-01-03 11:32:29

第二章?链表part02

  • ?24.?两两交换链表中的节点?
  • ?19.删除链表的倒数第N个节点?
  • ?面试题?02.07.?链表相交?
  • ?142.环形链表II?
  • ?总结

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

用虚拟头结点,这样会方便很多。?

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

文章讲解/视频讲解:?代码随想录

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

双指针的操作,要注意,删除第N个节点,那么我们当前遍历的指针一定要指向?第N个节点的前一个节点,建议先看视频。

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

文章讲解/视频讲解:代码随想录

?面试题?02.07.?链表相交??

本题没有视频讲解,大家注意?数值相同,不代表指针相同。

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

文章讲解:代码随想录

?142.环形链表II??

算是链表比较有难度的题目,需要多花点时间理解?确定环和找环入口,建议先看视频。

题目链接:142. 环形链表 II - 力扣(LeetCode)

文章讲解/视频讲解:代码随想录


? ? ? ? c++代码示例如下

ListNode* swapPairs(ListNode* head) {
    ListNode* dumHead = new ListNode(0);
    dumHead->next = head;
    ListNode* cur = dumHead;
    while (cur->next != nullptr && cur->next->next != nullptr) {
        ListNode* tmp1 = cur->next;
        ListNode* tmp2 = cur->next->next->next;

        cur->next = cur->next->next;
        cur->next->next = tmp1;
        cur->next->next->next = tmp2;

        cur = cur->next->next;
    }
    return dumHead->next;
}

? ? ? ? 双指针法,定义一个fast指针,一个slow指针。要删除倒数第n个节点,先让fast移动n步,然后fast和slow同时移动,直到fast指向链表末尾,此时删掉slow指向的节点即可。

注意细节:fast应该先走n+1步,为什么是n+1呢?因为只有这样同时移动的时候slow才能指向删除节点的上一个节点,方便做删除操作。

c++代码示例如下

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;
    while (fast != NULL) {
        fast = fast->next;
        slow = slow->next;
    }
    ListNode* tmp = slow->next;
    slow->next = slow->next->next;
    delete tmp;
    return dummyHead->next;
}

c++代码示例如下

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;
    if (lenB > lenA) {
        swap(lenA, lenB);
        swap(curA, curB);
    }
    int gap = lenA - lenB;
    while (gap--) {
        curA = curA->next;
    }
    while (curA != NULL) {
        if (curA == curB) {
            return curA;
        }
        curA = curA->next;
        curB = curB->next;
    }
    return NULL;
}

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

文章来源:https://blog.csdn.net/2302_79277225/article/details/135305282
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。