Reversing a linked list

Question

My problem is: Given a function to reverse a linked list.

My attempt at it in C was:

ListNode *reverse(ListNode *head)
{
    if(head == NULL || head->next == NULL)
        return head;

    ListNode *temp = head->next;
    ListNode *retP =  reverse(temp);
    temp->next = head;
    head->next = NULL;
    return retP;
}

But I do not think this is right. I want to be able to do it in Java and I am stumped on this. Any help would be appreciated. Please help me get started

see the following link: http://stackoverflow.com/questions/354875/reversing-a-linked-list-in-java-recursively — Ahsan Shah, Nov 17 '13 at 10:07
possible duplicate of [How to reverse a singly linked list using only two pointers?](http://stackoverflow.com/questions/1801549/how-to-reverse-a-singly-linked-list-using-only-two-pointers) — Rahul, Nov 17 '13 at 10:11
Of course, you would never need to write this, except perhaps in interviews. The simplest solution is to copy something which works if you ever had to, or use the built in function, so actually knowing the answer to this, and many other things which are better solved another way isn't worth knowing IMHO. — Peter Lawrey, Nov 17 '13 at 10:16

score 3 · Answer 1 · answered Nov 17 '13 at 10:08

3

If you want to reverse a List in Java, use

Collections.reverse(List list)

If you want to know how it is implemented or want to do it by hand, have a look at the JDK sources of java.util.Collections.

answered Nov 17 '13 at 10:08

Kai Sternad

22,214
7
47
42

score 0 · Answer 2 · answered Nov 17 '13 at 10:03

Iteratively

public reverseListIteratively (Node head) {
if (head == NULL || head.next == NULL)
return;  //empty or just one node in list

Node Second = head.next;

//store third node before we change 
Node Third = Second.next;  

//Second's next pointer
Second.next = head;  //second now points to head
head.next = NULL;  //change head pointer to NULL

//only two nodes, which we already reversed
if (Third == NULL)
return;  

Node CurrentNode = Third;

Node PreviousNode = Second;

while (CurrentNode != NULL)
{ 
Node NextNode = CurrentNode.next;

CurrentNode.next = PreviousNode;

/*  repeat the process, but have to reset
     the PreviousNode and CurrentNode
*/

PreviousNode = CurrentNode;
CurrentNode = NextNode;  
}

head  = PreviousNode; //reset the head node
}

Recursively

public void recursiveReverse(Node currentNode )
{  
 //check for empty list 
 if(currentNode == NULL)
    return;

/* if we are at the TAIL node:
    recursive base case:
 */
if(currentNode.next == NULL) 
{ 
//set HEAD to current TAIL since we are reversing list
head = currentNode; 
return; //since this is the base case
}

recursiveReverse(currentNode.next);
currentNode.next.next = currentNode;
currentNode.next = null; //set "old" next pointer to NULL
}

Source, with explanation (after using google for 3 seconds) http://www.programmerinterview.com/index.php/data-structures/reverse-a-linked-list/

score 0 · Answer 3 · answered Nov 17 '13 at 10:17

0

public Node reverse(Node node){
    Node p=null, c=node, n=node;
    while(c!=null){
        n=c.next;
        c.next=p;
        p=c;
        c=n;
    }
return p;
}

answered Nov 17 '13 at 10:17

Trying

14,004
9
70
110

Reversing a linked list

3 Answers3