labuladong日常刷题-递归魔法 | LeetCode 25K个一组翻转链表 234回文链表 | 双指针 167两数之和-II 输入有序数组

递归(迭代)操作链表

LeetCode 25 K个一组翻转链表 2023.12.27

• 题目链接
• labuladong讲解[链接]
  

ListNode* reverseKGroup(ListNode* head, int k) {
    //当k为1时不反转，那么将head直接返回
    if(k == 1)
        return head;
    //递归退出条件，当前不够k个节点时，返回head，不反转；够的话，找到下一次递归的头结点
    ListNode* post = head;
    for(int i = 0; i < k; i++)
    {
        if(post == NULL)
            return head;
        post = post->next;
    }
    //记录head-next，因为其要更新为下次递归回来的节点
    ListNode* temp = head->next;
    //head->next更新为下次递归的返回头结点，因为head变成了尾节点
    head->next = reverseKGroup(post, k);
    //记录temp->next，因为temp->next要更新为head
    post = temp->next;
    temp->next = head;
    //开始循环改变节点方向(next)
    for(int i = 2; i < k; i++)
    {
        //先记录要被改变的节点
        ListNode* temp1 = post->next;
        //改变朝向
        post->next = temp;
        //更新temp post 
        temp = post;
        post = temp1;
    }
    //返回当前递归的最后一个节点
    return temp;
}

LeetCode 234 回文链表 2023.12.27

• 题目链接
• labuladong讲解[链接]
  

bool isPalindrome(ListNode* head) {
    //思想：找到后半段链表，将其反转与前半段比较，所有相同返回true，有不同返回false
    //只有一个节点，返回true
    if(head->next == NULL)
        return true;
    //寻找中间节点，奇数个节点时为最中间的节点；偶数时，为中间那对右边的节点
    ListNode* slow = head;
    ListNode* fast = head;
    while(fast != NULL && fast->next != NULL)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    //right记录后半段开始比较的首节点
    ListNode* right = NULL;
    //偶数时确实是slow节点
    if(fast == NULL)
        right = slow;
    //奇数时为slow的下一个节点
    else if(fast != NULL && fast->next == NULL)
        right = slow->next;
    //开始翻转，用pre节点表示反转后链表尾部的空节点
    ListNode* pre = NULL;
    //循环条件，遍历节点不为空
    while(right)
    {
        //先记录将要丢失的节点
        ListNode* temp = right->next;
        //反转
        right->next = pre;
        //更新前一个节点与下一次遍历的节点
        pre = right;
        right = temp;
    }
    //反转后的头结点为pre，right节点为空
    //遍历翻转后的节点值与前半段值是否相等，存在不相等则输出false；否则最终输出true
    while(pre)
    {
        if(pre->val != head->val)
            return false;
        pre = pre->next;
        head = head->next;
    }
    return true;
}

双指针操作数组

LeetCode 167 两数之和-II 输入有序数组 2023.12.27

• 题目链接
• labuladong讲解[链接]
  

vector<int> twoSum(vector<int>& numbers, int target) {
    /*超时了！！！
        int index1 = 0, index2 = 0;
        for(int i = 0; i < numbers.size(); i++)
        {
            index1 = i;
            if(find(numbers.begin(), numbers.end(), target-numbers[i]) != numbers.end())
            {
                index2 = find(numbers.begin(), numbers.end(), target-numbers[i]) - numbers.begin();
                if(index1 != index2)
                    break;
                if(index2 == index1 && index1+1 < numbers.size() && numbers[index1+1] == numbers[index1])
                {
                    index2 = index1+1;
                    break;
                }
            }
        }
        return vector<int>{index1+1, index2+1};
        */
    //双指针，因为是有序数组且一定有答案
    //对向遍历，初始化为两端
    int index1 = 0, index2 = numbers.size()-1;
    //当不等的时候继续遍历
    while(numbers[index1]+numbers[index2] != target)
    {
        //如果相加值比目标值小，则说明numbers[index1]较小，index1++
        if(numbers[index1]+numbers[index2] < target)
            index1++;
        //如果相加值比目标值大，则说明numbers[index2]较小，index2--
        else
            index2--;
    }
    //注意数组下标题意是从1开始，所以需要索引值+1
    return vector<int>{index1+1, index2+1};
}