I am trying to reverse sublist of LinkedList, which is only even number of list. For example: if the list is [1, 2, 8, 9, 12, 16], the even subparts of the list are [2, 8] and [12, 16]. This would result in the new list, [1, 8, 2, 9, 16, 12].

This is my code, but it is not running I am getting time limit exceeded.

Node reverseMain(Node head) {

    Node current = head;
    int start=1;
    List<Integer> arr = new ArrayList<>();
    
    while(current.next != null){
      if(current.data%2 == 0)
        arr.add(start);
      start  ;
      current=current.next;
    }
    
    int begin=0, end=0;
    
    if(arr.size()>0){
      begin = arr.get(0);
      end = arr.get(arr.size()-1);
    }
    
    return reverseLinkedList(head, begin, end);
  }
  
  
  Node reverseSubList(Node head, int start, int end){
    Node current = head;
    Node next = null;
    
    Node old = null;
    for(int i=0; i<start; i  ){
      old = current;
      current = current.next;
    }
    
    while(start<=end && current!=null){
      next = current.next;
      current.next = old;
      old = current;
      current = next;
    }
    
    return old;
  }

CodePudding user response：

Here's how you can tackle the problem:

1. Identify the startIndex and endIndex for every even sublist of this list. You can store each of these values in a List<Int>, so you would have two lists startIndexes and endIndexes.

2. Use this efficient algorithm to reverse each of the sublists, which is defined by its start and end position.

CodePudding user response：

Your solution is both incorrect and inefficient.

1. you collect the indices of all even numbers in the linked list into arr (btw, poor name choice for a list). this means you will revert all indices from first even number to the last. so from [1, 2, 8, 9, 12, 16], the result will be [1, 16, 12, 9, 8, 2]. after you find an even number, you should search for odd number to establish a sublist.

2. reverseSubList needlessly starts iteration from head. also, there is no need to collect all the indices of the sublist. you just need to maintain a pointer at the start and end of the sublist and use them as start and end of reversal. so you set start of sublist pointer when you first encounter an even number. then you continue iterate but now you are searching for the first odd number to set end of sublist pointer. when you have set both pointers you call reverse. then you continue iterate on the sublist, searching for even number, and so on.