LeetCode Day8

LeetCode Day8

链表

¶翻转链表

/**
 * 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* reverseList(ListNode* head) {
        if (head == NULL) return head;
        ListNode* dummyHead = new ListNode(0, head);
        ListNode* tail = dummyHead->next;
        ListNode* temp;
        while (tail->next != NULL) {
            temp = tail->next;
            tail->next = temp->next;
            temp->next = dummyHead->next;
            dummyHead->next = temp;
        }
        head = dummyHead->next;
        return head;
    }
};

/*
* 思路：
* 先构造头结点
* 不断把后面的元素前插到单链表头结点的后面
* 使得反转过程就是前插的一个过程
*/

/*
* 随想录中的思路：
* 改变链表的next指针的指向，直接将链表反转 
*/

/* 双指针法 */

/* 首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null
* 把 cur->next 节点用 tmp 指针保存一下，也就是保存一下这个节点
* 为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了
* 将 cur->next 指向 pre ，此时已经反转了第一个节点了
* 接下来，就是循环走如下代码逻辑了，继续移动 pre 和 cur 指针
* 最后，cur 指针已经指向了 null，循环结束，链表也反转完毕了
* 此时我们 return pre 指针就可以了，pre 指针就指向了新的头结点
*/

ListNode* reverseList(ListNode* head) {
    ListNode* cur = head;
    ListNode* pre = nullptr;
    ListNode* temp;
    while (cur != NULL) {
        temp = cur->next;   // 保存 cur->next，作更新 cur 之用
        cur->next = pre;    // 翻转操作
        pre = cur;          // 先更新 pre
        cur = temp;         // 后更新 cur
    }
    head = pre; return head;
}
// 时间复杂度: O(n) 空间复杂度: O(1)

/* 递归法 */

/* 把双指针法中两个指针的更新写成递归 */
ListNode* reverse(ListNode* pre,ListNode* cur){
    if(cur == NULL) return pre;   // 递归出口
    ListNode* temp = cur->next;
    cur->next = pre;              // 翻转操作
    // 可以和双指针法的代码进行对比，如下递归的写法，其实就是做了这两步
    // pre = cur;
    // cur = temp;
    return reverse(cur,temp);
}

ListNode* reverseList(ListNode* head) {
    // 和双指针法初始化是一样的逻辑
    // ListNode* cur = head;
    // ListNode* pre = NULL;
    return reverse(NULL, head);
}
// 时间复杂度: O(n), 要递归处理链表的每个节点
// 空间复杂度: O(n), 递归调用了 n 层栈空间

/* 从后往前翻转的递归 */
ListNode* reverseList(ListNode* head) {
    // 边缘条件判断
    if(head == NULL) return NULL;
    if (head->next == NULL) return head;

    // 递归调用，翻转第二个节点开始往后的链表
    ListNode *last = reverseList(head->next);
    // 翻转头节点与第二个节点的指向
    head->next->next = head;
    // 此时的 head 节点为尾节点，next 需要指向 NULL
    head->next = NULL;
    return last;
}
// 时间复杂度: O(n)
// 空间复杂度: O(n)

¶两两交换链表中的节点

/**
 * 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, head);
        ListNode* pre, * cur1, * cur2;
        pre = dummyHead;

        while (pre->next != nullptr && pre->next->next != nullptr) {
            cur1 = pre->next;
            cur2 = cur1->next;

            pre->next = cur2;
            cur1->next = cur2->next;
            cur2->next = cur1;

            pre = cur1;
        }
        head = dummyHead->next;
        return head;
    }
};

/* 
* 画图，分清步骤先后即可 
* 注意不要非法内存引用
*/

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

/**
 * 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:
    static int cnt;
    void removeNode(ListNode* pre) {
        ListNode* temp = pre->next;
        pre->next = pre->next->next;
        delete(temp);
    }

    void findN(ListNode* node) {
        if (node == nullptr) return;
        findN(node->next);
        if (!(cnt--)) removeNode(node);
    }

    ListNode* removeNthFromEnd(ListNode* head, int n) {
        cnt = n;
        ListNode* dummyHead = new ListNode(0, head);
        ListNode* cur = dummyHead;
        findN(cur);
        head = dummyHead->next;
        return head;
    }
};
int Solution::cnt = 0;

/* 能过，但很拉
* 想到了回溯和静态变量
* 通过这俩结合找到要删除元素的前一个元素
* 然后执行删除
*/

/* 比较合适的是用快慢指针法 */
/* 快慢指针还可以检测链表是否有环，即答qwq */
/* 快指针走慢指针的两倍速，相遇即有环（无环不可能相遇） */

/* 
* 快慢指针法来解
* 就是让 fastIndex 先走 n 步， 然后 slowIndex 再和其一起走
* 直到 fastIndex 走到链表的最后一个结点
* 即 fastIndex->next == nullptr 时
* 此时 slowIndex 就走到了倒数第 n 个结点的前一个结点
* 开始删除操作
*/
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* fastIndex, * slowIndex;
        ListNode* dummyHead = new ListNode(0, head);
        fastIndex = dummyHead; slowIndex = dummyHead;
        while (n--) { fastIndex = fastIndex->next; }
        while (fastIndex->next != NULL) {
            fastIndex = fastIndex->next;
            slowIndex = slowIndex->next;
        }
        ListNode* temp = slowIndex->next;
        slowIndex->next = slowIndex->next->next;
        delete(temp);
        head = dummyHead->next;
        return head;
    }
};

¶相交链表

/**
 * 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* IntersectionNode = NULL;
        ListNode* dummyHeadA = new ListNode(0); 
        dummyHeadA->next = headA;
        ListNode* dummyHeadB = new ListNode(0);
        dummyHeadB->next = headB;
        ListNode* indexA = dummyHeadA, * indexB = dummyHeadB;
        int sizeA = 0, sizeB = 0;
        while (indexA->next != nullptr) { sizeA++; indexA = indexA->next; }
        while (indexB->next != nullptr) { sizeB++; indexB = indexB->next; }
        indexA = dummyHeadA, indexB = dummyHeadB;
        int n = abs(sizeA - sizeB);
        if (sizeA > sizeB) while (n--) { indexA = indexA->next; }
        if (sizeA < sizeB) while (n--) { indexB = indexB->next; }
        while (indexA != nullptr && indexB != nullptr) {
            if (indexA == indexB) {
                IntersectionNode = indexA;
                break;
            }
            indexA = indexA->next, indexB = indexB->next;
        }
        return IntersectionNode;
    }
};

/* 
* 是指针相等而不是数值相等
* 让较长的链表的指针先走一个长度差
* 这样两边对齐后就可以一起走
* 边走边判断两边指针是否相等
*/

¶环形链表

/**
 * 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* firstnodeofcycle = NULL;
        ListNode* fast = head, * 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;
                }
                firstnodeofcycle = index1;
                return firstnodeofcycle;
            }
        }
        return firstnodeofcycle;
    }
};

/* 测试程序 */ 
void printCycle(ListNode* head) {
    ListNode* firstNodeOfCycle = detectCycle(head);
    // if (firstNodeOfCycle != NULL) printf("%d\n", firstNodeOfCycle->val);
    if (firstNodeOfCycle == NULL) { printf("No Cycle\n"); return; }
    ListNode* temp = firstNodeOfCycle;
    do
    {
        printf("%d ", temp->val);
        temp = temp->next;
    } while (temp != firstNodeOfCycle);
    printf("\n");
}

int main() {
    ListNode* node_1 = new ListNode(-4);
    ListNode* node_2 = new ListNode(0, node_1);
    ListNode* node_3 = new ListNode(2, node_2);
    ListNode* head = new ListNode(3, node_3);
    // printList(head);

    node_1->next = node_3;
    // printList(head);

    printCycle(head);

    return 0;
}

/* 
* 分解成两个问题
* 先判断链表是否有环
* 若有环，找到这个环的入口
*/

补充：为什么第一次在环中相遇，slow的 步数 是 x + y 而不是 x + 若干环的长度 + y

¶总结

个人总结

来自代码随想录