链表中的节点每K个一组翻转_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