Reversing a linked list in Java, recursively

by

There’s code in one reply that spells it out, but you might find it easier to start from the bottom up, by asking and answering tiny questions (this is the approach in The Little Lisper):

  1. What is the reverse of null (the empty list)? null.
  2. What is the reverse of a one element list? the element.
  3. What is the reverse of an n element list? the reverse of the rest of the list followed by the first element.
public ListNode Reverse(ListNode list)
{
    if (list == null) return null; // first question

    if (list.next == null) return list; // second question

    // third question - in Lisp this is easy, but we don't have cons
    // so we grab the second element (which will be the last after we reverse it)

    ListNode secondElem = list.next;

    // bug fix - need to unlink list from the rest or you will get a cycle
    list.next = null;

    // then we reverse everything from the second element on
    ListNode reverseRest = Reverse(secondElem);

    // then we join the two lists
    secondElem.next = list;

    return reverseRest;
}

More Related Contents:

  1. How to detect a loop in a linked list?
  2. How do I create a Linked List Data Structure in Java? [closed]
  3. ArrayList Vs LinkedList
  4. Creating a LinkedList class from scratch
  5. Find all available combinations
  6. ListIterator Strange Adding to ArrayList
  7. Why does this recursive quick sort program not work? [closed]
  8. When to use LinkedList over ArrayList in Java?
  9. HashMap get/put complexity
  10. How to convert List to Map?
  11. What are Generics in Java? [closed]
  12. Calculate size of Object in Java [duplicate]
  13. Why start an ArrayList with an initial capacity?
  14. JAXB: How should I marshal complex nested data structures?
  15. Best way to create a hashmap of arraylist
  16. Factorial using Recursion in Java
  17. Recursive ConcurrentHashMap.computeIfAbsent() call never terminates. Bug or “feature”?
  18. understanding basic recursion
  19. What exactly is bucket in hashmap?
  20. What is a non recursive solution for Fibonacci-like sequence in Java?
  21. Finding Max value in an array using recursion
  22. Generating all permutations of a certain length
  23. Sorted array list in Java
  24. Permutation algorithm without recursion? Java
  25. How do I instantiate a Queue object in java?
  26. How to determine if binary tree is balanced?
  27. How to implement a Median-heap
  28. The simplest algorithm for poker hand evaluation
  29. Is LinkedList thread-safe when I’m accessing it with offer and poll exclusively?
  30. Recursion in JSF (c:forEach vs. ui:repeat)

Leave a Comment