LeetCode25:K个一组翻转链表

1、题目描述

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

  k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

  你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例1：

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

示例2：

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

提示：

• 表中的节点数目为n。
• 1<=k<=n<=5000
• 0<=Node.val<=1000

2、解题思路

• 只要剩余的结点数量大于k个，我们就一直执行头插法。
• 新创建一个临时节点dummy，并赋值dummy.next=head,让head称为它的下一个结点，这样无论链表变成什么样子，我们都可以执行返回return dummy.next。
• 执行头插法，其实每次循环只需要执行k-1次头插法即可。
• prev指向需要翻转的前一个结点，也就说把prev所指向的结点当作头插法的头结点，依次执行k-1次头插，循环结束之后，赋值prev=curr，让prev继续指向下一次需要翻转结点的前一个结点，也就是说让prev一直是头插法的头。

  这块可能画个示意图比较简单，直接描述会忽略很多细节，不过想法都是一样的。

3、代码实现

单链表节点类

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;
    }
    //遍历单链表
    public static void list(ListNode listNode){
        while(listNode!=null){
            System.out.print(listNode.val+" ");
            listNode=listNode.next;
        }
        System.out.println();
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

算法实现：

//leetcode25:K个一组翻转链表
public class LeetCode25 {
    public static  ListNode reverseKGroup(ListNode head,int k){
        ListNode dummy = new ListNode(0, head);
        ListNode prev=dummy;
        while(true){
            //检查剩余节点是否有k个，不足则返回
            ListNode last=prev;
            for (int i = 0; i < k; i++) {
                last=last.next;
                if(last==null){
                    return dummy.next;
                }
            }
            //翻转k个节点(使用类似头插法比较简单)
            ListNode curr=prev.next;
            ListNode p;
            //每次翻转执行k-1次头插
            for (int i = 0; i < k - 1; i++) {
                p=curr.next;
                curr.next=p.next;
                p.next=prev.next;
                prev.next=p;
            }
            prev=curr;  //prev重新指向下一次需要翻转的前一个结点
        }
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
        ListNode l3 = new ListNode(3);
        ListNode l4 = new ListNode(4);
        ListNode l5 = new ListNode(5);
        l1.next=l2;
        l2.next=l3;
        l3.next=l4;
        l4.next=l5;
        ListNode listNode = reverseKGroup(l1, 2);
        //遍历
        ListNode.list(listNode);
    }
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

上面我们2个一组翻转单链表，结果如下：

不过这个我感觉借助栈来实现也是可以的，每次入栈k个再出栈k个就行。