25.k sets of flipped linked lists

Train of thought Change the direction of the list + Group inversion

    class Solution {
    
        public ListNode reverseKGroup(ListNode head, int k) {
    

            //  Create a protection node 
            ListNode protect = new ListNode(-1, head);
            ListNode last = protect;

            while(head != null) {
    

                //  Get the node tail 
                //  If you don't do that ,  such as   Only left 2 Nodes ,  But to return 3 Group ,  It'll go straight back null
                ListNode tail = getTail(head, k);

                //  The boundary problem  : tail = null ,  The last group is not satisfied  k  individual 
                if (tail == null) {
    
                    break;
                }

                //  Record the next node of the tail node 
                ListNode nextNode = tail.next;

                //  reverse  head  To  tail  Between  n - 1  side 
                reverse(head, tail);

                //  The tail of the previous group ( Head before reverse ) Point to the head of the current group ( The tail before it is reversed )
                last.next = tail;
                head.next = nextNode;

                //  Move backward 
                last = head;
                head = nextNode;

            }

            return protect.next;
        }

        public ListNode getTail(ListNode head, int k){
    

            int walk = k - 1; //  The actual number of steps to take 

            if(walk <= 0) {
    
                return head;
            }

            for(int i = 0; head != null && i < walk; i++ ) {
    
                head = head.next;
            }

            return head;
        }

        private void reverse(ListNode head, ListNode tail){
    

            if (head == tail) {
    
                return;
            }

            //  Note here ,  We don't need to change the direction of the edge of the first node 
            //  So originally  last = null => last = head ,  Move back a bit 
            ListNode last = head;
            head = head.next;
            while(head != tail) {
    
                ListNode nextNode = head.next;
                //  Change the direction of the edge 
                head.next = last;
                //  The pointer moves back 
                last = head;
                head = nextNode;
            }
            //  Be careful  head  Move to  tail  When in position ,  The direction of the last edge has not changed 
            tail.next = last;
        }
    }

The basic idea is as follows :

The main idea is very simple , Group to reverse the linked list of the corresponding part , Then consider the links to the front and back nodes of the current group

First We want to achieve one Get the tail of the linked list Methods :

• Pass in head and The number of linked lists n Returns the end of the linked list

        public ListNode getTail(ListNode head, int k){
    

            int walk = k - 1; //  The actual number of steps to take 

            if(walk <= 0) {
    
                return head;
            }

            for(int i = 0; head != null && i < walk; i++ ) {
    
                head = head.next;
            }

            return head;
        }

The code is simple , But pay attention to some details :

• We need to head Move k Step to tail , So the number of steps actually taken k - 1, Because the default is head On .
• head != null This condition , When The number of linked list nodes in the last group is less than k - 1 When , This is the time The cycle is not over yet , head You may have reached the end of the linked list , Be careful : here We are going to return to tail Not the end of the linked list , It is null

secondly We're going to The head and tail nodes of the linked list are passed into reverse Method to reverse the edge of the linked list , This idea and 206. Reverse a linked list The thinking is basically the same , But it's a little different

        private void reverse(ListNode head, ListNode tail){
    

            if (head == tail) {
    
                return;
            }

            //  Note here ,  We don't need to change the direction of the edge of the first node 
            //  So originally  last = null => last = head ,  Move back a bit 
            ListNode last = head;
            head = head.next;
            while(head != tail) {
    
                ListNode nextNode = head.next;
                //  Change the direction of the edge 
                head.next = last;
                //  The pointer moves back 
                last = head;
                head = nextNode;
            }
            //  Be careful  head  Move to  tail  When in position ,  The direction of the last edge has not changed 
            tail.next = last;
        }

Attention to detail :

Reverse linked list , The initial state last It's pointing null Of , If there is 5 Nodes , We're actually going to reverse 5 side , Contains a leading point to null The edge of

But in this question , We just need to reverse n - 1 side , Here's the picture , In fact, what we want to reverse is node 1 To node 2 Just the side of

Details : If head and tial Point to the same node , We don't need to reverse the edges

   if (head == tail) {
    
       return;
   }

then , We need to connect the inverted linked list with other nodes , Another thing to note , Let's consider the whole first , Consider the details , So let's consider the middle node , Because there is no boundary problem in the middle node :

 public ListNode reverseKGroup(ListNode head, int k) {
    

            //  Create a protection node 
            ListNode protect = new ListNode(-1, head);
            ListNode last = protect;

            while(head != null) {
    

                //  Get the node tail 
                //  If you don't do that ,  such as   Only left 2 Nodes ,  But to return 3 Group ,  It'll go straight back null
                ListNode tail = getTail(head, k);

                //  The boundary problem  : tail = null ,  The last group is not satisfied  k  individual 
                if (tail == null) {
    
                    break;
                }

                //  Record the next node of the tail node 
                ListNode nextNode = tail.next;

                //  reverse  head  To  tail  Between  n - 1  side 
                reverse(head, tail);

                //  The tail of the previous group ( Head before reverse ) Point to the head of the current group ( The tail before it is reversed )
                last.next = tail;
                head.next = nextNode;

                //  Move backward 
                last = head;
                head = nextNode;

            }

            return protect.next;
        }

First, you need to record the tail node before reversing the linked list 4 The next node of 5 : ListNode nextNode = tail.next; Because after the reversal , node 4 and 5 The connection between them is broken

The second is to reverse the linked list , Then connect the tail of the current group and the previous group with the head of the next group :

• The tail node of the previous group 1 Point to the inverted header node 4 ( The tail node before inversion ) : last.next = tail;
• The tail node of the current group 3 ( The head node before inversion ) Point to Previously recorded nodes 5 head.next = nextNode;

Finally, we need to revise last The node points to the tail node of the current group , modify head The node points to the next set of head nodes

 //  Move backward 
 last = head;
  head = nextNode;

In addition, pay attention to details : The last group is not satisfied k When it's time , We don't need to reverse , So when we get the tail Need to judge

   //  The boundary problem  : tail = null ,  The last group is not satisfied  k  individual 
                if (tail == null) {
    
                    break;
                }

The second is to protect nodes : The reason for having a protected node is , The problem we consider is to consider the nodes of the intermediate group , But for the head node , It has no nodes from the previous group , And cannot get last ( That is, the tail node of the previous group ) , But protecting nodes can solve the problem well :

At the beginning last Direct to protect The node can be , The head node also does not need to consider the boundary problem .

The complete code is as follows :

package cn.knightzz.leetcode.hard;

import cn.knightzz.link.ListNode;
import static cn.knightzz.link.utils.ListNodeUtils.*;

@SuppressWarnings("all")
public class LeetCode25 {
    

    class Solution {
    
        public ListNode reverseKGroup(ListNode head, int k) {
    

            //  Create a protection node 
            ListNode protect = new ListNode(-1, head);
            ListNode last = protect;

            while(head != null) {
    

                //  Get the node tail 
                //  If you don't do that ,  such as   Only left 2 Nodes ,  But to return 3 Group ,  It'll go straight back null
                ListNode tail = getTail(head, k);

                //  The boundary problem  : tail = null ,  The last group is not satisfied  k  individual 
                if (tail == null) {
    
                    break;
                }

                //  Record the next node of the tail node 
                ListNode nextNode = tail.next;

                //  reverse  head  To  tail  Between  n - 1  side 
                reverse(head, tail);

                //  The tail of the previous group ( Head before reverse ) Point to the head of the current group ( The tail before it is reversed )
                last.next = tail;
                head.next = nextNode;

                //  Move backward 
                last = head;
                head = nextNode;

            }

            return protect.next;
        }

        public ListNode getTail(ListNode head, int k){
    

            int walk = k - 1; //  The actual number of steps to take 

            if(walk <= 0) {
    
                return head;
            }

            for(int i = 0; head != null && i < walk; i++ ) {
    
                head = head.next;
            }

            return head;
        }

        private void reverse(ListNode head, ListNode tail){
    

            if (head == tail) {
    
                return;
            }

            //  Note here ,  We don't need to change the direction of the edge of the first node 
            //  So originally  last = null => last = head ,  Move back a bit 
            ListNode last = head;
            head = head.next;
            while(head != tail) {
    
                ListNode nextNode = head.next;
                //  Change the direction of the edge 
                head.next = last;
                //  The pointer moves back 
                last = head;
                head = nextNode;
            }
            //  Be careful  head  Move to  tail  When in position ,  The direction of the last edge has not changed 
            tail.next = last;
        }
    }
}

Train of thought two Calculate the length of the list + Recursive inversion

The idea of this method is very simple : First calculate the length of the linked list , And then k Find the remainder to find the total number of groups to reverse , Then group and flip

Time complexity $O_n$

• Before implementing inversion n Method of item reverseN(ListNode head, int n)
• To reverse the first n To m The way to create an element : reverseBetwwen(ListNode head, int n , int m)
• Calculate the length of the list , Then the number of reversed groups is obtained by summing

/** * 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 = 1;
            ListNode p = head;

            while(p.next != null) {
    
                p = p.next;
                count++;
            }

            int nums = count / k;

            int left = 1;
            int right = k;
            ListNode node = head;
            for (int i = 0; i < nums; i++) {
    
                node = reverseBetween(node, left, right);
                left += k;
                right+= k;
            }
            return node;
        }

        public ListNode reverseBetween(ListNode node, int  left, int right) {
    

            if (node == null || node.next == null || left >= right) {
    
                return node;
            }

            int count = left;
            //  Create a virtual head node  [ The key ]
            ListNode pre = new ListNode(-1, node);
            ListNode p = pre;

            while(count != 1) {
    
                p = p.next;
                count--;
            }

            ListNode head = reverseN(p.next,right - left + 1);
            p.next = head;

            return pre.next;
        }

        public ListNode reverseN(ListNode head, int n){
    

            //  The boundary conditions 
            if (n == 1) {
    
                return head;
            }

            //  Turn back the head of the linked list 
            ListNode tail = reverseN(head.next, n - 1);
            //  Flip the head of the linked list  ,  Be careful  tail.next = null /  The first  n + 1  Nodes 
            ListNode p = head.next;

            //  as a result of   If the order is reversed , tail The target pointed to will be lost 
            head.next = p.next;
            p.next = head;
            return tail;
        }

    }