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

发布时间:2023年12月27日

递归(迭代)操作链表

LeetCode 25 K个一组翻转链表 2023.12.27

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

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

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};
}

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