LeetCode-206 K个一组反转链表

淡淡的烟草味﹌ 2023-10-03 21:32 20阅读 0赞

#### 问题描述 ####

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。**不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。**  
![在这里插入图片描述][f2b1d41e41f142ef91335a15a0426bcc.png]

> 输入：head = \[1,2,3,4,5\], k = 2  
> 输出：\[2,1,4,3,5\]

在做过反转链表后，这题最直观的解法就是将其拆分为K个子链表进行反转，再依次将这些子链表拼接起来。  
首先是反转链表

public static ListNode resverse(ListNode head){
        
            if (head == null) return null;
            ListNode cur = head;
            ListNode temp = null;
            ListNode dummy = new ListNode(0, null);
            while(cur!=null){
        
                temp = cur.next;
                cur.next = dummy.next;
                dummy.next = cur;
                cur = temp;
            }
            return dummy.next;
        }

再原地反转K个一组，断开，反转，连接三步走：  
![在这里插入图片描述][d0005bb066b344b19b8fdd7f7f28cda7.jpeg_pic_center]

public static ListNode reverseKGroup(ListNode head, int k) {
        
            ListNode dummy = new ListNode(0, head);
            ListNode end = dummy;
            ListNode pre = dummy;
            while (end!=null){
        
                ListNode start = pre.next;
                for (int i = 0; i < k && end != null; i++) {
        
                    end = end.next; // end跑到待反转链表末端
                }
                if (end == null) break;
                ListNode next = end.next; // 提前保存好未反转链表的始端
                end.next = null; // 断开
                pre.next = resverse(start); // 反转，拼接
                // 下一轮反转节点赋值
                start.next = next; 
                pre = start;
                end = start;
            }
            return dummy.next;
        }

[f2b1d41e41f142ef91335a15a0426bcc.png]: https://img-blog.csdnimg.cn/f2b1d41e41f142ef91335a15a0426bcc.png
[d0005bb066b344b19b8fdd7f7f28cda7.jpeg_pic_center]: https://img-blog.csdnimg.cn/d0005bb066b344b19b8fdd7f7f28cda7.jpeg#pic_center