Leecode 25. K 个一组翻转链表

雨点打透心脏的1/2处 2023-01-16 09:51 113阅读 0赞

### 文章目录 ###

*  题目
 *  题解
 *  代码

# 题目 #

> 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。  
> k 是一个正整数，它的值小于或等于链表的长度。  
> 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。  
> 进阶：  
> 你可以设计一个只使用常数额外空间的算法来解决此问题吗？  
> 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

# 题解 #

也是跟反转联表一样，先储存值，如果k是1的话，直接返回  
使用变量去递增，如果能整除说明到位了，截断然后反转，如果无法整除又遍历到头，那直接添加值

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODMzNjY1OA_size_16_color_FFFFFF_t_70]

# 代码 #

class Solution { 
        public ListNode reverseKGroup(ListNode head, int k) { 
            if(head==null){ 
                return head;
            }
            if(k==1){ 
                return head;
            }
            List<Integer> list = new ArrayList<>();
            List<Integer> resultList = new ArrayList<>();
            list.add(head.val);
            ListNode node = head;
            int i =2 ;
            while(node.next!=null){ 
                list.add(node.next.val);
                if(i%k==0){ 
                    resultList.addAll(getList(list));
                    list= new ArrayList();
                }
                i++;
                node=node.next;
                if(node.next==null){ 
                    resultList.addAll(list);
                }
            }
            
            node = head;
            int a = 0 ;
            while(node.next!=null){ 
                node.val = resultList.get(a);
                a++;
                node=node.next;
                if(node.next==null){ 
                    node.val = resultList.get(resultList.size()-1);
                }
            }
    
            return head;
        }
        
        public static List<Integer> getList(List<Integer> list){ 
            List<Integer> result = new ArrayList<>();
            for(int i = list.size()-1;i>=0;i--){ 
                result.add(list.get(i));
            }
            return result;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODMzNjY1OA_size_16_color_FFFFFF_t_70]: /images/20221022/a0e0b2a9e5504aba9b896cf14c9f6273.png