Является ли это плохим решением для обращения вспять связанного списка?

Question

/** 
* Definition for singly-linked list. 
* public class ListNode { 
*  int val; 
*  ListNode next; 
*  ListNode(int x) { val = x; } 
* } 
*/ 


public class Solution { 
    public ListNode reverseList(ListNode head) { 
     if(head == null){ 
      return head; 
     } 
     ListNode temp = new ListNode(head.val); 
     head = head.next; 
     while(head != null){ 
      ListNode nxt = new ListNode(head.val); 
      nxt.next = temp; 
      temp = nxt; 
      head = head.next; 
     } 
     return temp; 
    } 
} 

Для реверсирования связанного списка это работает, но я не удовлетворен, как я могу сделать лучше? Это кажется плохим решением, если честно, занимая пространство в каждом цикле.

Answer 1

Collections.reverse(List<?>)

, если это не удовлетворяющее вас проверить другие методы внутри этого класса

Answer 2

Да, это не является оптимальным решением для создания и добавления узлов для изменения связанного списка.

См. http://algorithms.tutorialhorizon.com/reverse-a-linked-list/. Хорошее объяснение доступно.

Answer 3

Вы можете использовать рекурсию вместо

public void reverse(ListNode prev, ListNode currNode) { 
     if (currNode == null) { 
      return; 
     } else { 
      reverse(currNode, currNode.next); 
      currNode.next = prev; 
     } 
    } 

Теперь вы можете вызвать reverse(null, headNode) обратить его на месте