Topic describes

Enter a linked list, reverse the list, output the new list header.

The input

{1, 2, 3, 4, 5}Copy the code

The return value

{5,43,2,1}
Copy the code

The problem solving

Reverse (); reverse(); reverse(); Reverse (); Reverse (); reverse(); They provide a direct inversion API for collections and strings. All you need is to build the set from the list, reverse the set, and then rebuild the list pointing relationship. The code is as follows:

public static ListNode reverseByList(ListNode head) {
        // the method first evaluates the input parameter
        if (head == null) {
            return null;
        }
        // Only one element is returned directly
        if (head.next == null) {
            return head;
        }
        List<ListNode>  list=new ArrayList<>();
        while(head! =null){
            list.add(head);
            head=head.next;
        }
        // Reverse Collections directly
        Collections.reverse(list);
        // Rebuild the pointing relationship after the inversion
        for(int i=0; i<list.size()-1; i++){ list.get(i).next=list.get(i+1);
        }
        // Next is empty for the last element of the list
        list.get(list.size()-1).next=null;
        return list.get(0);

    }
Copy the code

The above method does solve the problem, but it is not usually a test of your API proficiency, and the interviewer will ask you to reverse the process yourself. For the inversion of sets, the general algorithm realized by itself is to swap the positions of elements whose index is I and whose index is size-1-i. The set schematic diagram is as follows:

The set inversion code is implemented as follows:

public static void reverseList(List<ListNode> list){
         // If there are only 0 or 1 elements, no processing is required
         if(list.size()<=1) {return;
         }
         int size=list.size();
         int half=(size-1) > >1;
   			// Select * from size (I) to size (0)
         for(inti=half; i>=0; i--){ ListNode temp=list.get(size-1-i);
             list.set(size-1-i,list.get(i)); list.set(i,temp); }}Copy the code

For the linked list inversion, the above linked list inversion idea is to convert the set, reverse the position of the set, and then rebuild the pointer to. A more efficient way to reverse only linked lists is to simply change the pointer. Use a pre to hold a pointer to the previous node and a current pointer to the current traversal node. Change the current pointer pointer directly from pointing to the next node to pointing to the previous node. The schematic diagram is as follows:

The code implementation is as follows:

  public static ListNode reverseLinkNode(ListNode head) {
          // the method first evaluates the input parameter
          if (head == null) {
              return null;
          }
          // Only one element is returned directly
          if (head.next == null) {
              return head;
          }
  				// Keep the previous pointer for current
          ListNode pre = null;
          ListNode current = head;
          //temp is used to hold the pointer to the next node of the current node so that traversal continues
          ListNode temp;
          while(current ! =null) {
              temp = current.next;
              current.next = pre;
              pre = current;
              current = temp;
          }
          // Since current is null at the end of the loop, the head of the list should be pre, i.e. the last non-empty node
          return pre;
      }
Copy the code

Any other ideas? In addition to swapping symmetrically positioned elements when the set is reversed, it is also reasonable to use the stack to reverse the set, if you consider the FILO feature of stack, but with an additional stack space of n size. The time complexity is order n. In Java you need a stack and you can do that with LinkedList.

conclusion

There are two main ideas for list inversion:

One is to directly change the pointer implementation of linked list node, that is, the pointer pointing to the next node is changed to the previous node. This time complexity is O(n), space complexity is O(1), traversal is completed in one time, high efficiency.

Another way to turn linked lists into Collections is to reverse them directly using Java’s collections.reverse (), swap header and tail elements, or use the FILO feature of LinkedList to add and remove them using addLast and pollLast methods, respectively. The time complexity is O(n), the space complexity is O(n) (because creating a new list requires space, the stack also needs space), the overall efficiency of the linked list inversion is not as good as the first method.

I am also thinking of a slogan, look at others with a slogan at the end of the look very hanging, look at others.

I’m Kobayashi, and I’m good at diagrams.

I’m Aobing. The more you know, the more you don’t know.

I am a little sister, a person who will not allow you to go astray.

Me? Lost in thought… 😑