LeetCode刷题笔记(JAVA)——025K 个一组翻转链表

LeetCode刷题笔记(JAVA)——025K 个一组翻转链表 K 个一组翻转链表

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

笨方法￣□￣｜｜
剪切链表→反转链表→拼接链表

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode();
        int length = getLength(head);
        for (int i = 0; i < length / k; ++i) {
            ListNode listNode2 = cutListNode2(head, k);
            ListNode listNode1 = cutListNode1(head, k);
            ListNode newHead = reverseListNode(listNode1);
            dummy = mergeTwoListNode(dummy, newHead);
            head = listNode2;
        }
        dummy = mergeTwoListNode(dummy, head);
        return dummy.next;
    }

    public ListNode reverseListNode(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        } else {
            ListNode newHead = reverseListNode(head.next);
            head.next.next = head;
            head.next = null;
            return newHead;
        }
    }

    public int getLength(ListNode head) {
        int length = 1;
        if (head == null) {
            return 0;
        } else if (head.next == null) {
            return 1;
        }
        for (int i = 0; i < 5000; ++i) {
            if (head.next != null) {
                length++;
                head = head.next;
            } else {
                break;
            }
        }
        return length;
    }

    
    public ListNode cutListNode2(ListNode head, int k) {
        ListNode current = head;
        for (int i = 1; i < k; ++i) {
            current = current.next;
        }
        return current.next;
    }

    
    public ListNode cutListNode1(ListNode head, int k) {
        ListNode current = head;
        for (int i = 1; i < k; ++i) {
            current = current.next;
        }
        current.next = null;
        return head;
    }

    
    public ListNode mergeTwoListNode(ListNode listNode1, ListNode listNode2) {
        ListNode current = listNode1;
        for (int i = 0; i < getLength(listNode1); ++i) {
            current = current.next;
        }
        current.next = listNode2;
        return listNode1;
    }
}