当前位置:   article > 正文

链表中的节点每K个一组翻转_c 语言编程 给你一个链表,每k个节点一组进行翻转 csdn

c 语言编程 给你一个链表,每k个节点一组进行翻转 csdn

链表中的节点每K个一组翻转

将给出的链表中的节点每 k 个一组翻转,返回翻转后的链表
如果链表中的节点数不是 k 的倍数,将最后剩下的节点保持原样
你不能更改节点中的值,只能更改节点本身。

数据范围: 0≤n≤2000 , 1≤k≤2000 ,链表中每个元素都满足 0≤val≤1000
要求空间复杂度 O(1),时间复杂度 O(n)
例如:
给定的链表是 1→2→3→4→5
对于 k = 2 , 你应该返回 2→1→4→3→5
对于 k = 3 , 你应该返回 3→2→1→4→5
示例1
输入:
{1,2,3,4,5},2
复制
返回值:
{2,1,4,3,5}

思路:对于链表的问题,一定要弄清楚哪个变量的作用,不要一个变量多用,例如,用一个变量ln指向链表的头部,每次循环指向下一个元素,那么这个变量就用作定位链表的元素,这个变量每次指向的元素如果需要取出来,那么就新创建一个变量用于存放,不要重复使用。

对于本题而言,首先判断不反转的情况:1)当k大于链表的长度时,不用反转;2)当k为1的时候,不用反转。
代码如下:

ListNode ln = head;
        int cnt = 0;//用来记录链表的长度
        while(ln!=null){
            cnt += 1;
            ln = ln.next;
        }
        if(cnt<k){
            return head;
        }
        if(k == 1){
            return head;
        }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

当需要反转的时候,那么此时需要一个变量记录链表长度,然后每反转一次,长度就减少k,当长度小于k的时候,就代表不需要反转了。

其中,每次反转就是将链表中的元素先取出来,放入集合中,取出k个后再反转集合元素,再构造一个新的子链表,最后将每个子链表连接起来就得到所需的结果。

每次反转的代码如下:

//不反转是sum<k,那么反转就是大于等于
        ln = head;//ln重新指向链表头部
        ListNode subHead = new ListNode();//创建一个子链表的头节点
        ListNode subln = subHead;//subln指向子链表的头节点,并且将反转后的子链表插入至subln
        List<ListNode> list = new ArrayList<>();//用来存放待反转节点
        while (sum>=k){
            //每一次反转
            //先取出待反转的k个元素
            for (int i = 0; i < k; i++) {
                ListNode temp = ln;//取出ln指向的元素
                ln = ln.next;//ln指向链表下一个元素
                temp.next = null;//取出的元素必须要断尾,不然取出的不是节点元素而是以该节点为头的链表
                //并且断尾要在ln指向下一个节点之后,不然ln就指向null了
                list.add(temp);
            }
            Collections.reverse(list);//反转
            //通过list构建子链表
            //边界情况,不需要到最后一个元素
            for(int i = 0;i<list.size()-1;i++){
                list.get(i).next = list.get(i+1);
            }
            subln.next = list.get(0);
            subln = list.get(list.size()-1);//指向链表尾部的元素
            //此时需要更新循环条件以及清空集合
            list.clear();
            sum -= k;
        }
        //此时的ln指向剩下的元素构成的链表或者是null,需要接着subln
        subln.next = ln;
        //返回表头,注意此时表头是subhead.next;
        return subHead.next;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31

下面是完整的代码:

public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
        //计算链表长度
        int sum = 0;
        ListNode ln = head;//ln指向head的每个节点,目前指向头节点
        while(ln!=null){
            sum++;
            ln = ln.next;
        }
        //判断是否需要反转
        if(sum<k){
            return head;
        }
        if(k == 1){
            return head;
        }
        //不反转是sum<k,那么反转就是大于等于
        ln = head;//ln重新指向链表头部
        ListNode subHead = new ListNode();//创建一个子链表的头节点
        ListNode subln = subHead;//subln指向子链表的头节点,并且将反转后的子链表插入至subln
        List<ListNode> list = new ArrayList<>();//用来存放待反转节点
        while (sum>=k){
            //每一次反转
            //先取出待反转的k个元素
            for (int i = 0; i < k; i++) {
                ListNode temp = ln;//取出ln指向的元素
                ln = ln.next;//ln指向链表下一个元素
                temp.next = null;//取出的元素必须要断尾,不然取出的不是节点元素而是以该节点为头的链表
                //并且断尾要在ln指向下一个节点之后,不然ln就指向null了
                list.add(temp);
            }
            Collections.reverse(list);//反转
            //通过list构建子链表
            //边界情况,不需要到最后一个元素
            for(int i = 0;i<list.size()-1;i++){
                list.get(i).next = list.get(i+1);
            }
            subln.next = list.get(0);
            subln = list.get(list.size()-1);//指向链表尾部的元素
            //此时需要更新循环条件以及清空集合
            list.clear();
            sum -= k;
        }
        //此时的ln指向剩下的元素构成的链表或者是null,需要接着subln
        subln.next = ln;
        //返回表头,注意此时表头是subhead.next;
        return subHead.next;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48

这道题目有很多值得学习的地方:
1.操作链表的时候,定义变量的作用一定要清晰,单一,不要一个变量多用,容易混乱
2.掌握统计链表长度的方法:

//计算链表长度
        int sum = 0;
        ListNode ln = head;//ln指向head的每个节点,目前指向头节点
        while(ln!=null){
            sum++;
            ln = ln.next;
        }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

3.掌握取出链表中的元素,一个每次循环指向下一个节点的变量,一个临时变量用来存储节点,指向下一个节点后再将当前节点的next置为null。

for (int i = 0; i < k; i++) {
                ListNode temp = ln;//取出ln指向的元素
                ln = ln.next;//ln指向链表下一个元素
                temp.next = null;//取出的元素必须要断尾,不然取出的不是节点元素而是以该节点为头的链表
                //并且断尾要在ln指向下一个节点之后,不然ln就指向null了
                list.add(temp);
            }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

4.掌握将单个节点组成新的链表:

for(int i = 0;i<list.size()-1;i++){
                list.get(i).next = list.get(i+1);
            }
  • 1
  • 2
  • 3

5.新链表的连接:先创建新链表的表头,然后再定义一个变量指向当前链表的表尾,每次向表尾插入元素:

subln.next = list.get(0);
            subln = list.get(list.size()-1);//指向链表尾部的元素
  • 1
  • 2
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Monodyee/article/detail/86955
推荐阅读
相关标签
  

闽ICP备14008679号