25. K 个一组翻转链表

朱雀 2022-09-09 04:36 177阅读 0赞

[https://leetcode-cn.com/problems/reverse-nodes-in-k-group/][https_leetcode-cn.com_problems_reverse-nodes-in-k-group]

难度困难1264

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

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

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

**进阶：**

*  你可以设计一个只使用常数额外空间的算法来解决此问题吗？
 *  **你不能只是单纯的改变节点内部的值**，而是需要实际进行节点交换。

**示例 1：**

![868dadaff97fdd4fbe776d09af8a348f.png][]

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

**示例 2：**

![e91fa04bf9f00bc2fb7ad639a5203494.png][]

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

**示例 3：**

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

**示例 4：**

输入：head = [1], k = 1
    输出：[1]

**提示：**

*  列表中节点的数量在范围 `sz` 内
 *  `1 <= sz <= 5000`
 *  `0 <= Node.val <= 1000`
 *  `1 <= k <= sz`

通过次数216,607提交次数330,127

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public ListNode reverseKGroup(ListNode head, int k) {
            ListNode new_head = new ListNode();
            ListNode node = new_head;
            ListNode temp;
            ListNode xlen = head;
            int n = k;
            int len =0;
            while(xlen!=null)
            {
                len++;
                xlen = xlen.next;
            }
    
            len = len/k;
    
            while(head!=null)
            {
                temp = head.next; 
                head.next = new_head.next;
                new_head.next = head;
                head = temp;
                n--;
                if(n==0)
                {
                     
                    while(n<k)
                    {
                        
                        new_head = new_head.next;
                        n++; 
                    }
                    len--;
                    if(len==0)
                    {
                        new_head.next = head;
                        break;
                    }
                } 
                if(len==0) break;
            }       
            // show(node);
            return node.next;
        }
    
          void show(ListNode h)
        {
            while(h!=null)
            {
                 System.out.print(h.val +"  ");
                 h=h.next;
            }
            System.out.println();
        }
    }

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5Yqq5Yqb5a2m5Lmg55qE5qKF5a2Q_size_16_color_FFFFFF_t_70_g_se_x_16][]

[https_leetcode-cn.com_problems_reverse-nodes-in-k-group]: https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
[868dadaff97fdd4fbe776d09af8a348f.png]: /images/20220829/49ec532415f74f919a653c21377fd937.png
[e91fa04bf9f00bc2fb7ad639a5203494.png]: /images/20220829/22a04329c3ff4eb1aa0fa3ccd5b59679.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5Yqq5Yqb5a2m5Lmg55qE5qKF5a2Q_size_16_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/865753f51d154b2e80e2a8e7269ca9e8.png