Java K 个一组翻转链表

K 个一组翻转链表

困难

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

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

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

示例 1

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

输出[2,1,4,3,5]

示例 2

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

输出[3,2,1,4,5]

题解

因为在同一个方法操作所以辅助节点较多

ListNode dummy = new ListNode(0);// 记录最后链表返回节点

ListNode d = dummy; // 用于操作dummy把节点插入dummy形成链表

int count = 0; // 用于记录链表节点数

ListNode temp = head; // 用于帮助遍历链表记录节点数

int index = count / k;// while循环遍历次数也就是需要翻转多少组链表

ListNode t = head;// 遍历链表把值存入栈

stack.push(t.val);// 入栈

d.next = new ListNode((Integer) stack.pop(),null);// 出栈数作为节点值存入链表

最后拼接翻转后的链表与不满足翻转个数节点链表

思路首先用一个变量count记录链表个数再用一个变量index记录k个一组翻转次数

用一个while循环根据index<1作为结束条件因为index<1说明没有满足k个一组翻转条件在每一次满足的情况下把这几个节点入栈操作出栈就能拿到它们翻转后的值但是这里栈中存的是值所以取出都需要把值作为新建节点的值next就为空辅助接点后移就能在下次拼接好在执行完最后把翻转好的链表与剩余链表拼接就是最终答案了。

/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 记录节点个数
        int count = 0;
        ListNode dummy = new ListNode(0);
        ListNode d = dummy;
        // 栈存放节点
        Stack stack = new Stack();
        // 辅助节点
        ListNode temp = head;
        // 遍历链表
        while (true){
            if(temp == null){
                break;
            }
            count++;
            temp = temp.next;
        }
        System.out.println(count);// 打印节点个数
        int index = count / k;//有多少组翻转链表
        ListNode t = head;
        while (true){
            // 存入栈
            for (int i = 0; i < k; i++) {
                stack.push(t.val);
                t = t.next;//节点后移
                System.out.println("t"+t);
            }
            // 出栈
            for (int i = 0; i < k; i++) {
                d.next = new ListNode((Integer) stack.pop(),null);
                d = d.next;//节点后移
                System.out.println("d"+d);
            }
            index--;
            if(index<1){
                d.next = t;//链表拼接
                break;
            }
        }

        System.out.println(dummy.next);
        return dummy.next;
    }
}