您现在的位置是:首页 >其他 >C++ | LeetCode 24. 两两交换链表中的节点、19.删除链表的倒数第N个节点、面试题 02.07. 链表相交、142.环形链表II网站首页其他

C++ | LeetCode 24. 两两交换链表中的节点、19.删除链表的倒数第N个节点、面试题 02.07. 链表相交、142.环形链表II

zhf_flash 2024-06-30 18:01:02
简介C++ | LeetCode 24. 两两交换链表中的节点、19.删除链表的倒数第N个节点、面试题 02.07. 链表相交、142.环形链表II

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

  • 为啥最开始需要将current节点指向虚拟头结点,是因为想要交换节点1和节点2的值,虚拟头结点、节点1和节点2的指向都需要发生改变。
  • 需要注意的是,当改变一个节点的next值后,原先的链接就没了。所以当需要改变一个节点的next值后,需要先将该节点指向的节点先用临时变量存储下来。
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* virtualHead = new ListNode(0);
        virtualHead->next = head;
        ListNode* current = new ListNode(0);
        current = virtualHead;
        while(current->next != NULL && current->next->next != NULL) {
            ListNode* tmp1 = current->next;
            ListNode* tmp2 = current->next->next->next;
            current->next = current->next->next;
            current->next->next = tmp1;
            current->next->next->next = tmp2;
            current = current->next->next;
        }
        return virtualHead->next;
    }
};

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

  • 暴力解法:先计算链表的长度,然后转换成正着数 第(总数 - N)个节点。
  • 快慢指针法:让快节点先走 n 步, 然后快慢节点一块走,直到快节点走到末尾,那么慢节点即为所需要删除的节点。
  • 因为要删除某个节点,需要获取它的上一个节点,所以需要让慢节点少走一步,即等价于快节点多走一步。

暴力解法

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // 暴力解法
        ListNode* virtualHead = new ListNode(0);
        virtualHead->next = head;
        ListNode* current = virtualHead;
        int count = 0;
        while(current->next != NULL) {
            current = current->next;
            count++;
        }
        current = virtualHead;
        while((count - n) != 0) {
            current = current->next;
            count--;
        }
        ListNode* tmp = current->next;
        current->next = current->next->next;
        delete tmp;
        return virtualHead->next;
    }
};

快慢指针法

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // 快慢指针法
        // 让快节点先走 n 步, 然后快慢节点一块走,
        // 直到快节点走到末尾,那么慢节点即为所需要删除的节点
        ListNode* virtualHead = new ListNode(0);
        virtualHead->next = head;
        ListNode* fast = virtualHead;
        ListNode* slow = virtualHead;

        // 因为要删除某个节点,需要获取它的上一个节点,所以需要让慢节点少走一步,
        // 即等价于快节点多走一步
        n++; 
        // 在这里 fast != NULL 或者 fast->next != NULL 判断是否到达末尾的标志,
        // 两者都行,一个指向NULL,一个指向尾节点, 但是无论选择那个,都要保持一致,
        // 可以画个图梳理下,对于fast->next != NULL 就不需要n++了,
        // 因为两者同步移动的时候 较之第一个条件,会整体少走一步。
        while (n-- != 0 && fast != NULL) {  
            fast = fast->next;
        }
        while (fast != NULL) {
            fast = fast->next;
            slow = slow->next;
        }
        ListNode* tmp = slow->next;
        slow->next = slow->next->next;
        delete tmp;
        return virtualHead->next;
    }
};

面试题 02.07. 链表相交

  • 若两个链表相交,则从相交位置他们的后面的长度一定相等,所以需要先将两者的长度对齐,两个链表相当于是右对齐,即让长的链表先走,直到和短列表长度相等,然后在逐个节点去判断。
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* currentA = headA;
        ListNode* currentB = headB;

        int lengthA = 0;
        int lengthB = 0;
        while (currentA != NULL) {
            currentA = currentA->next;
            lengthA++;
        }
        while (currentB != NULL) {
            currentB = currentB->next;
            lengthB++;
        }

        currentA = headA;
        currentB = headB;

        int delta;
        if (lengthA > lengthB) {
            delta = lengthA - lengthB;
            while (delta-- != 0) {
                currentA = currentA->next;
            }
        } else if (lengthB > lengthA) {
            delta = lengthB - lengthA;
            while (delta-- != 0) {
                currentB = currentB->next;
            }
        } else;

        ListNode* interVal;
        while(currentA != NULL) {
            if (currentA == currentB) {
                interVal = currentA;
                return interVal;
            }
            else {
                interVal = NULL;
            }
            currentA = currentA->next;
            currentB = currentB->next;
        }
        return interVal;
    }
};

142.环形链表II

  • 暴力解法:将遍历的节点每次移动一个,就需要跟前面除自己的所有节点进行比对,是否有相等的,有则为环。简单粗暴但是效率太低。
  • 快慢指针法:非常巧妙的运用了数学的知识,通过类似于速度路程关系,可以推出两者在圈内相遇后,从相遇点到入环处和从起点到入环处的距离是一样的,基于此等式,即可得出。

暴力解法

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        // 暴力解法
        ListNode* currentA = head;
        ListNode* currentB = head;
        int count = 0;
        while(currentB != NULL) {
            currentB = currentB->next;
            count++;
            int tmpCount = count - 1;
            // B每次移动一个,就需要跟前面除自己的所有节点进行比对,是否有相等的,有则为环。
            currentA = head;
            while (tmpCount-- != 0 && currentA != currentB) {
                currentA = currentA->next;
            }
            if (tmpCount > 0) {
                return currentA;
            }
        }
        return NULL;
    }
};

快慢指针法

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        // 快慢指针法
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast != NULL && fast->next != NULL) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) {
                ListNode* index1 = head;
                ListNode* index2 = fast;
                while (index1 != index2) {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index1;
            }
        }
        return NULL;
    }
};
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。