leetcode 25 - k个一组反转链表_反转k个链表

题目：

方法一：

一段一段地反转，利用三个指针，pre, cur, next，pre指向以及转换好的最后一个节点，cur指向当前要转换的节点，，next指向下一个要转换的节点

public static ListNode reverseKGroup(ListNode head, int k) {
        if(head == null){
            return null;
        }
        int len = 0;
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode cur = dummyNode.next;
        while(cur != null){
            len++;
            cur = cur.next;
        }
        ListNode pre = dummyNode;
        cur = dummyNode.next;
        // 要转换的段数
        int n = len / k;
        while(n > 0 && cur != null){
            n--;
            //cur = dummyNode.next;
            ListNode next = cur.next;
            for(int i = 0; i < k - 1; i++){
                //System.out.println("cur.val = " + cur.next.val);
                cur.next = next.next;
                next.next = pre.next;
                pre.next = next;
                next = cur.next;
            }
            pre = cur;
            // 必不可少
            cur = cur.next;
            //print(dummyNode.next);
        }
        return dummyNode.next;
    }

方法二：

利用四个指针，pre, start, end, next，pre指向已经转换好的最后一个节点，start指向要开始转换的第一个节点，end指向最后一个要开始转换的节点，next指向下一段要开始转换的链表

// 穿针引线法
    public static ListNode reverseKGroup2(ListNode head, int k) {
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode start = dummyNode;
        ListNode pre = dummyNode;
        ListNode end = dummyNode;
        while(end.next != null){
            for(int i=0;i<k && end != null;i++){
                end = end.next;
            }
            if(end == null){
                break;
            }
 
            //要截取的区间
            start = pre.next;
            ListNode next = end.next;
            end.next = null;
 
            // 反转截取到的一段链表
            pre.next = reverseList(start);
            start.next = next;
 
            pre = start;
            end = pre;
        }
        return dummyNode.next;
    }
 
    // 链表反转 leetcode206  借助虚拟头节点
    public static ListNode reverseList(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode ans = new ListNode(-1);
        ListNode cur = head;
        while(cur != null){
            ListNode next = cur.next;
            cur.next = ans.next;
            ans.next = cur;
            cur = next;
        }
        // 返回的是 ans的下一个节点
        return ans.next;
    }