算法通关村-----K个一组反转链表

K 个一组翻转链表

问题描述

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。详见leetcode25

问题分析

可以采用头插法和穿针引线法来实现

头插法是指先建立一个虚拟头节点，然后从给定链表的头节点开始取K个节点，每次采用从头部插入的方式进行插入，之后再取K个节点，以上一次的末尾节点当作头节点按照头插法的方式进行插入，将最后不足K个的节点直接进行拼接，这样可以保证K个节点一组反转链表。

穿针引线法是指我们可以遍历给定链表，以K个为一组取下，然后将取下的K个元素的链表进行反转，反转后拼接回去。穿针引线发的思路很简单，但是要注意四个节点，pre,left,right,post，pre是拼接的前一个节点，post是拼接的后一个节点，left是反转前的第一个节点，right是反转前的最后一个节点。反转后,拼接时,pre.next = right,left.next=post。

代码实现

头插法实现

public ListNode reverseKGroup(ListNode head, int k) {
    //简化计算，先遍历获取链表长度
    int len = getLength(head);
    //计算需要反转的次数
    int n = len/k;
    //简历虚拟头节点
    ListNode vhead = new ListNode(-1);
    //current指向每次头插法插入的头节点
    ListNode current = vhead;
    //iter用于遍历给定链表
    ListNode iter = head;
    //n次反转
    for(int i=0;i<n;i++){
        //k个一组反转
        for(int j=0;j<k;j++){
            //记录需要遍历的下一个节点
            ListNode next = iter.next;
            //头插法进行节点插入
            iter.next = current.next;
            current.next = iter;
            //继续遍历
            iter = next;
        }
        //将current指向当前的最后一个节点，也是下次头插法的头节点
        for(int l=0;l<k;l++){
            current = current.next;
        }
    }
    //不足k个，直接拼接
    if(iter!=null){
        current.next = iter;
    }
    //返回k个一组反转后的链表
    return vhead.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

public int getLength(ListNode head){
    ListNode current = head;
    int count = 0;
    while(current!=null){
        count++;
        current = current.next;
    }
    return count;
}
1
2
3
4
5
6
7
8
9

穿针引线法实现

public ListNode reverseKGroup(ListNode head, int k) {
    //为了方便插入，简历虚拟头节点
    ListNode vhead = new ListNode(-1);
    //pre指向拼接时的前一个节点
    ListNode pre = vhead;
    //计算反转次数
    int n = getLength(head)/k;
    //current用于遍历给定链表
    ListNode current = head;
    //n次反转
    for(int i=0;i<n;i++){
        //left指向反转前的第一个元素
        ListNode left = current;
        //找到当前的第K个元素
        for(int j=0;j<k-1;j++){
            current = current.next;
        }
        //right指向反转前的最后一个元素
        ListNode right = current;
        //post指向拼接时的后一个节点
        ListNode post = current.next;
        //right必须置空，否则后面的元素会一起反转
        right.next = null;
        //反转
        right = reverse(left);
        //拼接
        pre.next = right;
        left.next = post;
        //下次拼接时的前一个节点变成left
        pre = left;
        //下一次反转从post开始计数
        current = post;
    }
    //最后不足K个，直接拼接
    if(current!=null){
        pre.next = current;
    }
    //返回反转结果
    return vhead.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

public ListNode reverse(ListNode head){
    ListNode pre = null;
    ListNode current = head;
    while(current!=null){
        ListNode next = current.next;
        current.next = pre;
        pre = current;
        current = next;
    }
    return pre;
}
1
2
3
4
5
6
7
8
9
10
11

public int getLength(ListNode head){
    ListNode current = head;
    int count = 0;
    while(current!=null){
        count++;
        current = current.next;
    }
    return count;
}
1
2
3
4
5
6
7
8
9