【CT】LeetCode手撕—25. K 个一组翻转链表

题目

• 原题连接：25. K 个一组翻转链表

1-思路

• 1. dummyHead：设置虚拟头结点，通过虚拟头结点保证每个结点的地位相同
• 2. 定位 pre 和 end 拆链：借助 pre 、start 和 end 指针：翻转 区间内的链表
  • 其中 pre 指针记录的是，被翻转部分的前一个结点
  • 其中 start 指针记录的是，被翻转链表的首节点
  • 其中 end 指针记录的是翻转链表的最后一个结点，end 一直移动
  • 2.1 定位 思路，利用循环定位 end
    • 2.1.1 while循环：利用 while 循环，只要 end.next != null
    • **2.1.2 判断是否满足k **：判断是否满足 k 个一组条件，令 i 从 1 开始遍历，遍历到 k ，同时 end != null 移动 end 。遇到 end 为 null 直接 break
  • 2.2 拆链
    • ① 先用 next 记录位置
    • ② 拆掉 end.next 断链
    • ③ 拆掉 pre.next
• 3. 翻转：翻转固定区间 start 和 end 内的链表
  • 3.1 翻转后用 pre.next 接收
  • 3.2 更新 pre 和 end 指针

2- 实现

⭐25. K 个一组翻转链表——题解思路

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 定义 pre 、end
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode pre = dummyHead;
        ListNode end = dummyHead;

        while(end.next!=null){
            // k 个一组
            for(int i = 0 ; i < k && end!=null ;i++){
                end = end.next;
            }

            if(end == null){
                break;
            }

            // start 
            ListNode start = pre.next;
            ListNode tmp = end.next;
            pre.next = null;
            end.next = null;
            pre.next = reverseList(start);

            // 更新 start  和 pre
            start.next = tmp;
            pre = start;
            end = start;
        }

        return dummyHead.next;
    }

    // 单链表翻转逻辑
    public ListNode reverseList(ListNode head){
        if(head==null || head.next == null){
            return head;
        }
        ListNode cur = reverseList(head.next);

        head.next.next = head;
        head.next = null;
        return cur;
    }
}

3- ACM实现

public class reverseList {

    // 链表
    static class ListNode{
        int val;
        ListNode next;
        ListNode(){}
        ListNode(int x){
            val = x;
        }
    }


    // k一组翻转
    public static ListNode reverseK(ListNode head,int k){
        // 定义dummyHead
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        ListNode pre = dummyHead;
        ListNode end = dummyHead;

        // 定位 end
        while(end.next!=null){
            // k 个一组
            for(int i = 0 ; i < k && end!=null; i++){
                end = end.next;
            }
            //
            if(end==null){
                break;
            }
            // 断链
            ListNode start = pre.next;
            ListNode tmp = end.next;
            pre.next = null;
            end.next = null;

            // 翻转
            pre.next = reverseL(start);

            // 更新 start 、 pre 和 end
            start.next = tmp;
            pre = start;
            end = start;
        }
        return dummyHead.next;
    }

    public static ListNode reverseL(ListNode head){
        if(head==null || head.next == null){
            return head;
        }

        ListNode cur = reverseL(head.next);
        head.next.next = head;
        head.next = null;
        return cur;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.println("输入链表长度");
        int n  = sc.nextInt();

        System.out.println("输入链表");
        ListNode head=null,tail=null;

        for(int i = 0 ; i < n ; i++){
            ListNode newNode = new ListNode(sc.nextInt());
            if(head==null){
                head = newNode;
                tail = newNode;
            }else{
                tail.next = newNode;
                tail = newNode;
            }
        }
        System.out.println("输入要以几个一组反转链表");
        int k = sc.nextInt();
        // 翻转后的链表
        ListNode forRes = reverseK(head,k);
        while (forRes!=null){
            System.out.print(forRes.val+" ");
            forRes = forRes.next;
        }
    }
}