美文网首页算法提高之LeetCode刷题
【LeetCode每日一题】25. Reverse Nodes

【LeetCode每日一题】25. Reverse Nodes

作者: 七八音 | 来源:发表于2020-07-25 23:00 被阅读0次

    25. Reverse Nodes in k-Group

    问题描述

    Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

    k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

    Example:

    Given this linked list: 1->2->3->4->5

    For k = 2, you should return: 2->1->4->3->5

    For k = 3, you should return: 3->2->1->4->5

    Note:

    • Only constant extra memory is allowed.
    • You may not alter the values in the list's nodes, only nodes itself may be changed.

    给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。

    k 是一个正整数,它的值小于或等于链表的长度。

    如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

    题解

    题目要求每k个节点一组进行翻转,返回反转后的链表。可以将算法分为两部分:分组+链表翻转;还要注意的是,如果剩余节点数目不够k个,不进行翻转,直接链接到上一组的链表上。

    步骤:

    1. 记录链表长度;
    2. 循环,条件是剩余链表长度不小于k
    3. 一边计数一边翻转:
      1. 使用指针pre表示上一次翻转结果的链表尾,如果还没有进行翻转,设置为新声明的dummy节点;
      2. 指针cur表示需要翻转的节点;初始设置为pre指针的下一个节点;
      3. 进行翻转:
        1. 声明temp指针:记录cur的下一个节点
        2. 进行单节点的翻转;
        3. pre指针的下一个节点始终表示当前组翻转的头结点,所以每次反转后都要更新pre的next指针;
    4. 更新pre指针为cur;(cur指针指向当前组的最后一个节点)
    5. 更新链表长度k;

    代码:

    /**
     * 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* reverseKGroup(ListNode* head, int k) {
            ListNode *first = new ListNode(-1), *pre = first, *cur = first;
            first->next = head;
            
            int len = 0;
            // 记录链表长度
            while (cur = cur->next) ++len;
            // 训练分组反转链表
            while (len >= k){
                //记录需要翻转链表的起始节点
                cur = pre->next;
                //依次翻转,对组内的k个节点翻转
                for (int i=1; i< k; ++i){
                    ListNode *temp = cur->next;
                    cur->next = temp->next;
                    temp->next = pre->next;
                    
                    pre->next = temp;
                }
                pre = cur;
                len -= k;
            }
            
            return first->next;
        }
    };
    

    没有想到这里的翻转方式;想到的是先找到k个节点的子链表;然后翻转,最后更新链接指针;这种方法应该也可以,过两天回顾时再看看。

    Reference

    https://www.cnblogs.com/grandyang/p/4441324.html


    欢迎关注公众号,一起学习

    相关文章

      网友评论

        本文标题:【LeetCode每日一题】25. Reverse Nodes

        本文链接:https://www.haomeiwen.com/subject/hsjvlktx.html