Flip linked lists in groups of K

Given a linked list, each k nodes in a group of flipped, please return to the flipped list.

K is a positive integer whose value is less than or equal to the length of the list.

If the total number of nodes is not an integer multiple of k, keep the last remaining nodes in the same order.

Advanced:

Can you design an algorithm that only uses constant extra space to solve this problem? You can’t just change the values inside the nodes, you need to actually swap nodes.

Examples can be found on the LeetCode website.

Source: LeetCode link: leetcode-cn.com/problems/re… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution 1: use stack
  • First of all, ifk=1orheadIs empty orheadNo successor node, return null;
  • Otherwise, traversing the head list, using a stack kListNode, pushes k nodes onto the stack at a time, and then removes K nodes in turn from the stack, and the list is arranged in the order that it is removed, until the traversal of the list is complete, i.e., the complete flip of all nodes.

Note: an empty node newHead record head node is recorded at the beginning, so when the traversal is completed, the next node directly returned to newHead is the flipped head node.

import java.util.Stack;

public class LeetCode_025 {
    public static ListNode reverseKGroup(ListNode head, int k) {
        if (k == 1 || head == null || head.next == null) {
            return head;
        }

        ListNode newHead;
        ListNode pre = new ListNode(-1);
        newHead = pre;
        pre.next = head;
        int count = 0;
        ListNode next = head;
        Stack<ListNode> kListNode = new Stack<>();
        while(next ! =null || count == k) {
            if (count == k) {
                while(! kListNode.isEmpty()) { pre.next = kListNode.pop(); pre = pre.next; } pre.next = next; count =0;
            } else {
                if(next ! =null) { kListNode.push(next); next = next.next; count++; }}}return newHead.next;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        ListNode result = reverseKGroup(head, 3);
        while(result ! =null) {
            System.out.print(result.val + ""); result = result.next; }}}Copy the code

Not every shell has a pearl, but the pearl must be in the shell, not everyone will be successful efforts, but successful people must be very hard.