Reversing a linked list in Java recursively

Question

I have been working on a Java project for a class for a while now  It is an implementation of a linked list  here called AddressList  containing simple nodes called ListNode   The catch is that everything would have to be done with recursive algorithms  I was able to do everything fine sans one method  public AddressList reverse        ListNode     public class ListNode    public String data    public ListNode next      Right now my reverse function just calls a helper function that takes an argument to allow recursion   public AddressList reverse      return new AddressList this reverse this head        With my helper function having the signature of private ListNode reverse ListNode current    At the moment  I have it working iteratively using a stack  but this is not what the specification requires  I had found an algorithm in C that recursively reversed and converted it to Java code by hand  and it worked  but I had no understanding of it   Edit  Nevermind  I figured it out in the meantime   private AddressList reverse ListNode current  AddressList reversedList     if current    null         return reversedList    reversedList addToFront current getData       return this reverse current getNext    reversedList       While I m here  does anyone see any problems with this route

User · Answer

Here s yet another recursive solution   It has less code within the recursive function than some of the others  so it might be a little faster   This is C  but I believe Java would be very similar   class Node lt T gt        Node lt T gt  next      public T data     class LinkedList lt T gt        Node lt T gt  head   null       public void Reverse                 if  head    null              head   RecursiveReverse null  head              private Node lt T gt  RecursiveReverse Node lt T gt  prev  Node lt T gt  curr                Node lt T gt  next   curr next          curr next   prev          return  next    null    curr   RecursiveReverse curr  next

User · Answer

As Java is always pass-by-value  to recursively reverse a linked list in Java  make sure to return the  new head  the head node after reversion  at the end of the recursion    static ListNode reverseR ListNode head        if  head    null    head next    null            return head             ListNode first   head      ListNode rest   head next          reverse the rest of the list recursively     head   reverseR rest           fix the first node after recursion     first next next   first      first next   null       return head

User · Answer

This solution demonstrates that no arguments are required          Reverse the list     return reference to the new list head     public LinkNode reverse         if  next    null            return this     Return the old tail of the list as the new head           LinkNode oldTail   next reverse       Recurse to find the old tail     next next   this     The old next node now points back to this node     next   null     Make sure old head has no next     return oldTail     Return the old tail all the way back to the top     Here is the supporting code  to demonstrate that this works   public class LinkNode       private char name      private LinkNode next                  Return a linked list of nodes  whose names are characters from the given string         param str node names             public LinkNode String str            if   str    null      str length      0                 throw new IllegalArgumentException  LinkNode constructor arg      str                     name   str charAt 0           if  str length    gt  1                next   new LinkNode str substring 1                         public String toString             return name     next    null         next toString                public static void main String   args            LinkNode head   new LinkNode  abc            System out println head           System out println head reverse

User · Answer

Here is a simple iterative approach   public static Node reverse Node root        if  root    null    root next    null            return root             Node curr  prev  next      curr   root  prev   next   null      while  curr    null            next   curr next          curr next   prev           prev   curr          curr   next            return prev      And here is a recursive approach    public static Node reverseR Node node        if  node    null    node next    null            return node             Node next   node next      node next   null       Node remaining   reverseR next       next next   node      return remaining

User · Answer

Inspired by an article discussing immutable implementations of recursive data structures I put an alternate solution together using Swift   The leading answer documents solution by highlighting the following topics    What is the reverse of nil  the empty list     Does not matter here  because we have nil protection in Swift   What is the reverse of a one element list    The element itself  What is the reverse of an n element list    The reverse of the second element on followed by the first element     I have called these out where applicable in the solution below        Node is a class that stores an arbitrary value of generic type T   and a pointer to another Node of the same time   This is a recursive   data structure representative of a member of a unidirectional linked  list      public class Node lt T gt        public let value  T     public let next  Node lt T gt        public init value  T  next  Node lt T gt              self value   value         self next   next            public func reversedList   - gt  Node lt T gt            if let next   self next                  3  The reverse of the second element on followed by the first element              return next reversedList     value           else                  2  Reverse of a one element list is itself             return self                          return Returns a newly created Node consisting of the lhs list appended with rhs value      public func   lt T gt  lhs  Node lt T gt   rhs  T  - gt  Node lt T gt        let tail  Node lt T gt       if let next   lhs next              The new tail is created recursively  as long as there is a next node          tail   next   rhs       else              If there is not a next node  create a new tail node to append         tail   Node lt T gt  value  rhs  next  nil               Return a newly created Node consisting of the lhs list appended with rhs value      return Node lt T gt  value  lhs value  next  tail

User · Answer

public class Singlelinkedlist     public static void main String   args        Elem list    new Elem        Reverse list     list is populate some  where or some how          this  is the part you should be concerned with the function Method has only 3 lines    public static void Reverse Elem e       if  e  null        if e next   null           Reverse e next         System out println e data          class Elem     public Elem next        Link to next element in the list    public String data      Reference to the data

User · Answer

Here is a simple iterative approach   public static Node reverse Node root        if  root    null    root next    null            return root             Node curr  prev  next      curr   root  prev   next   null      while  curr    null            next   curr next          curr next   prev           prev   curr          curr   next            return prev      And here is a recursive approach    public static Node reverseR Node node        if  node    null    node next    null            return node             Node next   node next      node next   null       Node remaining   reverseR next       next next   node      return remaining

User · Answer

Reverse by recursive algo   public ListNode reverse ListNode head        if  head    null    head next    null  return head          ListNode rHead   reverse head next       rHead next   head      head   null      return rHead      By iterative  public ListNode reverse ListNode head        if  head    null    head next    null  return head          ListNode prev   null      ListNode cur   head     ListNode next   head next      while  next    null            cur next   prev          prev   cur          cur   next          next   next next            return cur

User · Answer

public class Singlelinkedlist     public static void main String   args        Elem list    new Elem        Reverse list     list is populate some  where or some how          this  is the part you should be concerned with the function Method has only 3 lines    public static void Reverse Elem e       if  e  null        if e next   null           Reverse e next         System out println e data          class Elem     public Elem next        Link to next element in the list    public String data      Reference to the data

User · Answer

I was asked this question at an interview and was annoyed that I fumbled with it since I was a little nervous   This should reverse a singly linked list  called with reverse head NULL   so if this were your list   1- 2- 3- 4- 5- null it would become  5- 4- 3- 2- 1- null         Takes as parameters a node in a linked list  and p  the previous node in that list       returns the head of the new list     Node reverse Node n Node p              if n  null  return null          if n next  null     if this is the end of the list  then this is the new head             n next p              return n                    Node r reverse n next n      call reverse for the next node                                           using yourself as the previous node         n next p                        Set your next node to be the previous node          return r                        Return the head of the new list             edit  ive done like 6 edits on this  showing that it s still a little tricky for me lol

User · Answer

I think this is more cleaner solution  which resembles LISP     Example     reverse0 1- gt 2- gt 3  null    gt           reverse0 2- gt 3  1    gt               reverse0 3  2- gt 1    gt  reverse0 null  3- gt 2- gt 1     once the first argument is null  return the second arg    which is nothing but the reveresed list   Link reverse0 Link f  Link n        if  f    null            Link t   new Link f data1  f data2            t nextLink   n                                f   f nextLink                 assuming first had n elements before                                          now it has  n-1  elements         reverse0 f  t             return n

User · Answer

Here is a reference if someone is looking for Scala implementation   scala gt  import scala collection mutable LinkedList import scala collection mutable LinkedList  scala gt  def reverseLinkedList A  ll  LinkedList A    LinkedList A             ll foldLeft LinkedList empty A    accumulator  nextElement    gt  nextElement    accumulator  reverseLinkedList   A  ll  scala collection mutable LinkedList A  scala collection mutable LinkedList A   scala gt  reverseLinkedList LinkedList  a    b    c    res0  scala collection mutable LinkedList java lang String    LinkedList c  b  a   scala gt  reverseLinkedList LinkedList  1    2    3    res1  scala collection mutable LinkedList java lang String    LinkedList 3  2  1

User · Answer

package com mypackage  class list       node first          node last       list        first null      last null       returns true if first is null   public boolean isEmpty        return first  null      Method for insertion    public void insert int value        if isEmpty             first last new node value           last next null            else          node temp new node value           last next temp          last temp          last next null             simple traversal from beginning   public void traverse        node t first      while  isEmpty    amp  amp  t  null           t printval            t  t next            static method for creating a reversed linked list   public static void reverse node n list l1        if n next  null          reverse n next l1    will traverse to the very end       l1 insert n value    every stack frame will do insertion now        private inner class node   private class node      int value      node next      node int value           this value value            void printval            System out print value

User · Answer

public void reverse        if isEmpty         return              Node lt T gt  revHead   new Node lt T gt          this reverse head next  revHead        this head   revHead     private Node lt T gt  reverse Node lt T gt  node  Node lt T gt  revHead       if node next    null          revHead next   node         return node              Node lt T gt  reverse   this reverse node next  revHead        reverse next   node       node next   null       return node

User · Answer

This is how we would do this in Opal - a pure functional programming language  And  IMHO - doing this recursively only makes sense in that context   List Reverse List l        if  IsEmpty l     Size l     1  return l      return reverse rest l    first l       rest l  returns a list that is the original list without it s first node  first l  returns the first element     is a concatenation operator

User · Answer

public void reverse         head   reverseNodes null  head      private Node reverseNodes Node prevNode  Node currentNode        if  currentNode    null          return prevNode      Node nextNode   currentNode next      currentNode next   prevNode      return reverseNodes currentNode  nextNode

User · Answer

I got half way through  till null  and one node as suggested by plinth   but lost track after making recursive call  However  after reading the post by plinth  here is what I came up with   Node reverse Node head         if head is null or only one node  it s reverse of itself    if    head  null      head next    null    return head        reverse the sub-list leaving the head node    Node reverse   reverse head next         head next still points to the last element of reversed sub-list       so move the head to end    head next next   head        point last node to nil   get rid of cycles    head next   null    return reverse

User · Answer

Reversing the linked list using recursion  The idea is adjusting the links by reversing the links     public ListNode reverseR ListNode p              Base condition  Once you reach the last node return p                                                    if  p    null    p next    null                 return p                     Go on making the recursive call till reach the last node now head points to the last node          ListNode head    reverseR p next      Head points to the last node           Here  p points to the last but one node previous node    q points to the last   node  Then next next step is to adjust the links         ListNode q   p next             Last node link points to the P  last but one node          q next   p            Set the last but node  previous node  next to null         p next   null           return head    Head points to the last node

User · Answer

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     What is the reverse of null  the empty list   null  What is the reverse of a one element list  the element  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

User · Answer

package com mypackage  class list       node first          node last       list        first null      last null       returns true if first is null   public boolean isEmpty        return first  null      Method for insertion    public void insert int value        if isEmpty             first last new node value           last next null            else          node temp new node value           last next temp          last temp          last next null             simple traversal from beginning   public void traverse        node t first      while  isEmpty    amp  amp  t  null           t printval            t  t next            static method for creating a reversed linked list   public static void reverse node n list l1        if n next  null          reverse n next l1    will traverse to the very end       l1 insert n value    every stack frame will do insertion now        private inner class node   private class node      int value      node next      node int value           this value value            void printval            System out print value

User · Answer

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     What is the reverse of null  the empty list   null  What is the reverse of a one element list  the element  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

User · Answer

The algo will need to work on the following model    keep track of the head Recurse till end of linklist Reverse linkage   Structure   Head           1-- gt 2-- gt 3-- gt 4-- gt N-- gt null  null-- gt 1-- gt 2-- gt 3-- gt 4-- gt N lt --null  null-- gt 1-- gt 2-- gt 3-- gt 4 lt --N lt --null  null-- gt 1-- gt 2-- gt 3 lt --4 lt --N lt --null  null-- gt 1-- gt 2 lt --3 lt --4 lt --N lt --null  null-- gt 1 lt --2 lt --3 lt --4 lt --N lt --null  null lt --1 lt --2 lt --3 lt --4 lt --N                                                 Head   Code   public ListNode reverse ListNode toBeNextNode  ListNode currentNode                           ListNode currentHead   currentNode     keep track of the head          if   currentNode  null   currentNode next  null   amp  amp  toBeNextNode   null return currentHead     ignore for size 0  amp  1          if  currentNode next  null currentHead   reverse currentNode  currentNode next      travarse till end recursively          currentNode next   toBeNextNode     reverse link          return currentHead      Output   head-- gt 12345  head-- gt 54321

User · Answer

The algo will need to work on the following model    keep track of the head Recurse till end of linklist Reverse linkage   Structure   Head           1-- gt 2-- gt 3-- gt 4-- gt N-- gt null  null-- gt 1-- gt 2-- gt 3-- gt 4-- gt N lt --null  null-- gt 1-- gt 2-- gt 3-- gt 4 lt --N lt --null  null-- gt 1-- gt 2-- gt 3 lt --4 lt --N lt --null  null-- gt 1-- gt 2 lt --3 lt --4 lt --N lt --null  null-- gt 1 lt --2 lt --3 lt --4 lt --N lt --null  null lt --1 lt --2 lt --3 lt --4 lt --N                                                 Head   Code   public ListNode reverse ListNode toBeNextNode  ListNode currentNode                           ListNode currentHead   currentNode     keep track of the head          if   currentNode  null   currentNode next  null   amp  amp  toBeNextNode   null return currentHead     ignore for size 0  amp  1          if  currentNode next  null currentHead   reverse currentNode  currentNode next      travarse till end recursively          currentNode next   toBeNextNode     reverse link          return currentHead      Output   head-- gt 12345  head-- gt 54321

User · Answer

this function reverses the linked list public Node reverseList Node p        if head    null           return null              make the last node as head     if p next    null           head next   null          head   p          return p              traverse to the last node  then reverse the pointers by assigning the 2nd last node to last node and so on       return reverseList p next  next   p

User · Answer

void reverse node1 node2   if node1 next  null        reverse node1 next node1      node1 next node2    call this method as reverse start null

User · Answer

private Node ReverseList Node current  Node previous                if  current    null  return null          Node originalNext   current next          current next   previous          if  originalNext    null  return current          return ReverseList originalNext  current

User · Answer

public static ListNode recRev ListNode curr        if curr next    null           return curr            ListNode head   recRev curr next       curr next next   curr      curr next   null          propogate the head value     return head

User · Answer

PointZeroTwo has got elegant answer  amp  the same in Java      public void reverseList        if head  null           head   reverseListNodes null   head            private Node reverseListNodes Node parent   Node child        Node next   child next      child next   parent      return  next  null  child reverseListNodes child  next

User · Answer

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     What is the reverse of null  the empty list   null  What is the reverse of a one element list  the element  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

User · Answer

Here is C  version of Reverse for linklist       public void Reverse                 Node currentNode  nextNode null  prevNode null          currentNode   head          while currentNode  null                        nextNode   currentNode next              currentNode next   prevNode              prevNode   currentNode              currentNode   nextNode                    head   prevNode

User · Answer

Recursive solution class SLL      int data     SLL next     SLL reverse SLL head        base case - 0 or 1 elements   if head    null    head next    null  return head     SLL temp   reverse head next     head next next   head    head next   null    return temp

User · Answer

public Node reverseListRecursive Node curr        if curr    null    Base case         return head            else           reverseListRecursive curr next   next    curr             return curr

User · Answer

PointZeroTwo has got elegant answer  amp  the same in Java      public void reverseList        if head  null           head   reverseListNodes null   head            private Node reverseListNodes Node parent   Node child        Node next   child next      child next   parent      return  next  null  child reverseListNodes child  next

User · Answer

Reverse by recursive algo   public ListNode reverse ListNode head        if  head    null    head next    null  return head          ListNode rHead   reverse head next       rHead next   head      head   null      return rHead      By iterative  public ListNode reverse ListNode head        if  head    null    head next    null  return head          ListNode prev   null      ListNode cur   head     ListNode next   head next      while  next    null            cur next   prev          prev   cur          cur   next          next   next next            return cur

User · Answer

Here is C  version of Reverse for linklist       public void Reverse                 Node currentNode  nextNode null  prevNode null          currentNode   head          while currentNode  null                        nextNode   currentNode next              currentNode next   prevNode              prevNode   currentNode              currentNode   nextNode                    head   prevNode

User · Answer

public Node reverseRec Node prev  Node curr        if  curr    null  return null         if  curr next    null            curr next   prev          return curr         else           Node temp   curr next           curr next   prev          return reverseRec curr  temp                            call using  head   reverseRec null  head

User · Answer

I know this is an old post  but most of the answers are not tail recursive i e  they do some operations after returning from the recursive call  and hence not the most efficient   Here is a tail recursive version   public Node reverse Node previous  Node current        if previous    null          return null      if previous equals head           previous setNext null       if current    null          end of list         head   previous          return head        else                       Node temp   current getNext            current setNext previous           reverse current  temp             return null       should never reach here       Call with   Node newHead   reverse head  head getNext

User · Answer

I was asked this question at an interview and was annoyed that I fumbled with it since I was a little nervous   This should reverse a singly linked list  called with reverse head NULL   so if this were your list   1- 2- 3- 4- 5- null it would become  5- 4- 3- 2- 1- null         Takes as parameters a node in a linked list  and p  the previous node in that list       returns the head of the new list     Node reverse Node n Node p              if n  null  return null          if n next  null     if this is the end of the list  then this is the new head             n next p              return n                    Node r reverse n next n      call reverse for the next node                                           using yourself as the previous node         n next p                        Set your next node to be the previous node          return r                        Return the head of the new list             edit  ive done like 6 edits on this  showing that it s still a little tricky for me lol

User · Answer

I got half way through  till null  and one node as suggested by plinth   but lost track after making recursive call  However  after reading the post by plinth  here is what I came up with   Node reverse Node head         if head is null or only one node  it s reverse of itself    if    head  null      head next    null    return head        reverse the sub-list leaving the head node    Node reverse   reverse head next         head next still points to the last element of reversed sub-list       so move the head to end    head next next   head        point last node to nil   get rid of cycles    head next   null    return reverse

User · Answer

As Java is always pass-by-value  to recursively reverse a linked list in Java  make sure to return the  new head  the head node after reversion  at the end of the recursion    static ListNode reverseR ListNode head        if  head    null    head next    null            return head             ListNode first   head      ListNode rest   head next          reverse the rest of the list recursively     head   reverseR rest           fix the first node after recursion     first next next   first      first next   null       return head

User · Answer

static void reverseList     if head  null  head next  null   ListNode tail head   head points to tail   ListNode Second head next  ListNode Third Second next  tail next null   tail previous head is poiniting null Second next tail  ListNode current Third  ListNode prev Second  if Third next  null          while current  null       ListNode    next current next          current next prev          prev current          current next              head prev   new head     class ListNode      public int data      public ListNode next      public int getData             return data             public ListNode int data            super            this data   data          this next null             public ListNode int data  ListNode next            super            this data   data          this next   next             public void setData int data            this data   data            public ListNode getNext             return next            public void setNext ListNode next            this next   next

User · Answer

What other guys done   in other post is a game of content  what i did is a game of linkedlist  it reverse the LinkedList s member not reverse of a Value of members   Public LinkedList reverse LinkedList List           if List    null                 return null         if List next      null                return List         LinkedList temp   this reverse  List next             return temp setNext  List

User · Answer

What other guys done   in other post is a game of content  what i did is a game of linkedlist  it reverse the LinkedList s member not reverse of a Value of members   Public LinkedList reverse LinkedList List           if List    null                 return null         if List next      null                return List         LinkedList temp   this reverse  List next             return temp setNext  List

User · Answer

I think this is more cleaner solution  which resembles LISP     Example     reverse0 1- gt 2- gt 3  null    gt           reverse0 2- gt 3  1    gt               reverse0 3  2- gt 1    gt  reverse0 null  3- gt 2- gt 1     once the first argument is null  return the second arg    which is nothing but the reveresed list   Link reverse0 Link f  Link n        if  f    null            Link t   new Link f data1  f data2            t nextLink   n                                f   f nextLink                 assuming first had n elements before                                          now it has  n-1  elements         reverse0 f  t             return n

User · Answer

public Node reverseRec Node prev  Node curr        if  curr    null  return null         if  curr next    null            curr next   prev          return curr         else           Node temp   curr next           curr next   prev          return reverseRec curr  temp                            call using  head   reverseRec null  head

User · Answer

I was asked this question at an interview and was annoyed that I fumbled with it since I was a little nervous   This should reverse a singly linked list  called with reverse head NULL   so if this were your list   1- 2- 3- 4- 5- null it would become  5- 4- 3- 2- 1- null         Takes as parameters a node in a linked list  and p  the previous node in that list       returns the head of the new list     Node reverse Node n Node p              if n  null  return null          if n next  null     if this is the end of the list  then this is the new head             n next p              return n                    Node r reverse n next n      call reverse for the next node                                           using yourself as the previous node         n next p                        Set your next node to be the previous node          return r                        Return the head of the new list             edit  ive done like 6 edits on this  showing that it s still a little tricky for me lol

User · Answer

public Node reverseListRecursive Node curr        if curr    null    Base case         return head            else           reverseListRecursive curr next   next    curr             return curr

User · Answer

This is how we would do this in Opal - a pure functional programming language  And  IMHO - doing this recursively only makes sense in that context   List Reverse List l        if  IsEmpty l     Size l     1  return l      return reverse rest l    first l       rest l  returns a list that is the original list without it s first node  first l  returns the first element     is a concatenation operator

User · Answer

Inspired by an article discussing immutable implementations of recursive data structures I put an alternate solution together using Swift   The leading answer documents solution by highlighting the following topics    What is the reverse of nil  the empty list     Does not matter here  because we have nil protection in Swift   What is the reverse of a one element list    The element itself  What is the reverse of an n element list    The reverse of the second element on followed by the first element     I have called these out where applicable in the solution below        Node is a class that stores an arbitrary value of generic type T   and a pointer to another Node of the same time   This is a recursive   data structure representative of a member of a unidirectional linked  list      public class Node lt T gt        public let value  T     public let next  Node lt T gt        public init value  T  next  Node lt T gt              self value   value         self next   next            public func reversedList   - gt  Node lt T gt            if let next   self next                  3  The reverse of the second element on followed by the first element              return next reversedList     value           else                  2  Reverse of a one element list is itself             return self                          return Returns a newly created Node consisting of the lhs list appended with rhs value      public func   lt T gt  lhs  Node lt T gt   rhs  T  - gt  Node lt T gt        let tail  Node lt T gt       if let next   lhs next              The new tail is created recursively  as long as there is a next node          tail   next   rhs       else              If there is not a next node  create a new tail node to append         tail   Node lt T gt  value  rhs  next  nil               Return a newly created Node consisting of the lhs list appended with rhs value      return Node lt T gt  value  lhs value  next  tail

User · Answer

Here s yet another recursive solution   It has less code within the recursive function than some of the others  so it might be a little faster   This is C  but I believe Java would be very similar   class Node lt T gt        Node lt T gt  next      public T data     class LinkedList lt T gt        Node lt T gt  head   null       public void Reverse                 if  head    null              head   RecursiveReverse null  head              private Node lt T gt  RecursiveReverse Node lt T gt  prev  Node lt T gt  curr                Node lt T gt  next   curr next          curr next   prev          return  next    null    curr   RecursiveReverse curr  next

User · Answer

public void reverse         head   reverseNodes null  head      private Node reverseNodes Node prevNode  Node currentNode        if  currentNode    null          return prevNode      Node nextNode   currentNode next      currentNode next   prevNode      return reverseNodes currentNode  nextNode

User · Answer

This solution demonstrates that no arguments are required          Reverse the list     return reference to the new list head     public LinkNode reverse         if  next    null            return this     Return the old tail of the list as the new head           LinkNode oldTail   next reverse       Recurse to find the old tail     next next   this     The old next node now points back to this node     next   null     Make sure old head has no next     return oldTail     Return the old tail all the way back to the top     Here is the supporting code  to demonstrate that this works   public class LinkNode       private char name      private LinkNode next                  Return a linked list of nodes  whose names are characters from the given string         param str node names             public LinkNode String str            if   str    null      str length      0                 throw new IllegalArgumentException  LinkNode constructor arg      str                     name   str charAt 0           if  str length    gt  1                next   new LinkNode str substring 1                         public String toString             return name     next    null         next toString                public static void main String   args            LinkNode head   new LinkNode  abc            System out println head           System out println head reverse

User · Answer

The solution is       package basic   import custom ds nodes Node   public class RevLinkedList    private static Node lt Integer gt  first   null   public static void main String   args        Node lt Integer gt  f   new Node lt Integer gt         Node lt Integer gt  s   new Node lt Integer gt         Node lt Integer gt  t   new Node lt Integer gt         Node lt Integer gt  fo   new Node lt Integer gt         f setNext s       s setNext t       t setNext fo       fo setNext null        f setItem 1       s setItem 2       t setItem 3       fo setItem 4       Node lt Integer gt  curr   f      display curr       revLL null  f       display first      public static void display Node lt Integer gt  curr        while  curr getNext      null            System out println curr getItem             System out println curr getNext             curr   curr getNext             public static void revLL Node lt Integer gt  pn  Node lt Integer gt  cn        while  cn getNext      null            revLL cn  cn getNext             break            if  cn getNext      null            first   cn            cn setNext pn

User · Answer

I was asked this question at an interview and was annoyed that I fumbled with it since I was a little nervous   This should reverse a singly linked list  called with reverse head NULL   so if this were your list   1- 2- 3- 4- 5- null it would become  5- 4- 3- 2- 1- null         Takes as parameters a node in a linked list  and p  the previous node in that list       returns the head of the new list     Node reverse Node n Node p              if n  null  return null          if n next  null     if this is the end of the list  then this is the new head             n next p              return n                    Node r reverse n next n      call reverse for the next node                                           using yourself as the previous node         n next p                        Set your next node to be the previous node          return r                        Return the head of the new list             edit  ive done like 6 edits on this  showing that it s still a little tricky for me lol

User · Answer

void reverse node1 node2   if node1 next  null        reverse node1 next node1      node1 next node2    call this method as reverse start null

User · Answer

public void reverseLinkedList Node node       if node  null           return             reverseLinkedList node next       Node temp   node next      node next node prev      node prev temp      return

User · Answer

Here is a reference if someone is looking for Scala implementation   scala gt  import scala collection mutable LinkedList import scala collection mutable LinkedList  scala gt  def reverseLinkedList A  ll  LinkedList A    LinkedList A             ll foldLeft LinkedList empty A    accumulator  nextElement    gt  nextElement    accumulator  reverseLinkedList   A  ll  scala collection mutable LinkedList A  scala collection mutable LinkedList A   scala gt  reverseLinkedList LinkedList  a    b    c    res0  scala collection mutable LinkedList java lang String    LinkedList c  b  a   scala gt  reverseLinkedList LinkedList  1    2    3    res1  scala collection mutable LinkedList java lang String    LinkedList 3  2  1

User · Answer

The solution is       package basic   import custom ds nodes Node   public class RevLinkedList    private static Node lt Integer gt  first   null   public static void main String   args        Node lt Integer gt  f   new Node lt Integer gt         Node lt Integer gt  s   new Node lt Integer gt         Node lt Integer gt  t   new Node lt Integer gt         Node lt Integer gt  fo   new Node lt Integer gt         f setNext s       s setNext t       t setNext fo       fo setNext null        f setItem 1       s setItem 2       t setItem 3       fo setItem 4       Node lt Integer gt  curr   f      display curr       revLL null  f       display first      public static void display Node lt Integer gt  curr        while  curr getNext      null            System out println curr getItem             System out println curr getNext             curr   curr getNext             public static void revLL Node lt Integer gt  pn  Node lt Integer gt  cn        while  cn getNext      null            revLL cn  cn getNext             break            if  cn getNext      null            first   cn            cn setNext pn

User · Answer

I know this is an old post  but most of the answers are not tail recursive i e  they do some operations after returning from the recursive call  and hence not the most efficient   Here is a tail recursive version   public Node reverse Node previous  Node current        if previous    null          return null      if previous equals head           previous setNext null       if current    null          end of list         head   previous          return head        else                       Node temp   current getNext            current setNext previous           reverse current  temp             return null       should never reach here       Call with   Node newHead   reverse head  head getNext

User · Answer

static void reverseList     if head  null  head next  null   ListNode tail head   head points to tail   ListNode Second head next  ListNode Third Second next  tail next null   tail previous head is poiniting null Second next tail  ListNode current Third  ListNode prev Second  if Third next  null          while current  null       ListNode    next current next          current next prev          prev current          current next              head prev   new head     class ListNode      public int data      public ListNode next      public int getData             return data             public ListNode int data            super            this data   data          this next null             public ListNode int data  ListNode next            super            this data   data          this next   next             public void setData int data            this data   data            public ListNode getNext             return next            public void setNext ListNode next            this next   next

User · Answer

The algo will need to work on the following model    keep track of the head Recurse till end of linklist Reverse linkage   Structure   Head           1-- gt 2-- gt 3-- gt 4-- gt N-- gt null  null-- gt 1-- gt 2-- gt 3-- gt 4-- gt N lt --null  null-- gt 1-- gt 2-- gt 3-- gt 4 lt --N lt --null  null-- gt 1-- gt 2-- gt 3 lt --4 lt --N lt --null  null-- gt 1-- gt 2 lt --3 lt --4 lt --N lt --null  null-- gt 1 lt --2 lt --3 lt --4 lt --N lt --null  null lt --1 lt --2 lt --3 lt --4 lt --N                                                 Head   Code   public ListNode reverse ListNode toBeNextNode  ListNode currentNode                           ListNode currentHead   currentNode     keep track of the head          if   currentNode  null   currentNode next  null   amp  amp  toBeNextNode   null return currentHead     ignore for size 0  amp  1          if  currentNode next  null currentHead   reverse currentNode  currentNode next      travarse till end recursively          currentNode next   toBeNextNode     reverse link          return currentHead      Output   head-- gt 12345  head-- gt 54321

User · Answer

public static ListNode recRev ListNode curr        if curr next    null           return curr            ListNode head   recRev curr next       curr next next   curr      curr next   null          propogate the head value     return head

User · Answer

Reversing the linked list using recursion  The idea is adjusting the links by reversing the links     public ListNode reverseR ListNode p              Base condition  Once you reach the last node return p                                                    if  p    null    p next    null                 return p                     Go on making the recursive call till reach the last node now head points to the last node          ListNode head    reverseR p next      Head points to the last node           Here  p points to the last but one node previous node    q points to the last   node  Then next next step is to adjust the links         ListNode q   p next             Last node link points to the P  last but one node          q next   p            Set the last but node  previous node  next to null         p next   null           return head    Head points to the last node

User · Answer

private Node ReverseList Node current  Node previous                if  current    null  return null          Node originalNext   current next          current next   previous          if  originalNext    null  return current          return ReverseList originalNext  current

User · Answer

public void reverse        if isEmpty         return              Node lt T gt  revHead   new Node lt T gt          this reverse head next  revHead        this head   revHead     private Node lt T gt  reverse Node lt T gt  node  Node lt T gt  revHead       if node next    null          revHead next   node         return node              Node lt T gt  reverse   this reverse node next  revHead        reverse next   node       node next   null       return node

User · Answer

The algo will need to work on the following model    keep track of the head Recurse till end of linklist Reverse linkage   Structure   Head           1-- gt 2-- gt 3-- gt 4-- gt N-- gt null  null-- gt 1-- gt 2-- gt 3-- gt 4-- gt N lt --null  null-- gt 1-- gt 2-- gt 3-- gt 4 lt --N lt --null  null-- gt 1-- gt 2-- gt 3 lt --4 lt --N lt --null  null-- gt 1-- gt 2 lt --3 lt --4 lt --N lt --null  null-- gt 1 lt --2 lt --3 lt --4 lt --N lt --null  null lt --1 lt --2 lt --3 lt --4 lt --N                                                 Head   Code   public ListNode reverse ListNode toBeNextNode  ListNode currentNode                           ListNode currentHead   currentNode     keep track of the head          if   currentNode  null   currentNode next  null   amp  amp  toBeNextNode   null return currentHead     ignore for size 0  amp  1          if  currentNode next  null currentHead   reverse currentNode  currentNode next      travarse till end recursively          currentNode next   toBeNextNode     reverse link          return currentHead      Output   head-- gt 12345  head-- gt 54321

User · Answer

Recursive solution class SLL      int data     SLL next     SLL reverse SLL head        base case - 0 or 1 elements   if head    null    head next    null  return head     SLL temp   reverse head next     head next next   head    head next   null    return temp

User · Answer

public void reverseLinkedList Node node       if node  null           return             reverseLinkedList node next       Node temp   node next      node next node prev      node prev temp      return

User · Answer

this function reverses the linked list public Node reverseList Node p        if head    null           return null              make the last node as head     if p next    null           head next   null          head   p          return p              traverse to the last node  then reverse the pointers by assigning the 2nd last node to last node and so on       return reverseList p next  next   p

User · Answer

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     What is the reverse of null  the empty list   null  What is the reverse of a one element list  the element  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

[java] Reversing a linked list in Java, recursively

Examples related to java

Examples related to data-structures

Examples related to recursion

Examples related to linked-list