Please correct my below code - Reverse a single linked list

general
, ,
1

struct Node* reverse(struct Node *head)
{

/*using temp below to traverse to end of linked list
and rev pointer will be new head of reversed linked list*/

struct Node *temp=NULL,*rev=NULL,*prev;
if (head==NULL)
    return rev;
if(head)
{
    if(rev==NULL)
    {
        temp=head;
        while(temp->next)
        {
            prev=temp;
            temp=temp->next;
        }
        rev=temp;
        prev->next=NULL;
    }
    else
    {
        while(head->next!=NULL)
        {
            temp=head;
            while(temp->next)
            {
                prev=temp;
                temp=temp->next;
            }
            prev->next=NULL;
            rev->next=temp;
        }
    }
}
return rev;

}

2

My solution For This Problem

3

I think you start out by breaking the list near the end, and then setting a lot of links to NULL, and maybe end up with just two items? … since rev never moves after the first loop takes it to the end of the original list.

Here’s a Python example of reversing a linked list. The basic idea is that you have two extra pointers, here called mid and fore, plus the root pointer moving (behind them) through the list. After the process, root is pointing at the other end and all the list pointers are reversed.


if root:
    mid = root.link
    root.link = None
    while mid:
        fore = mid.link
        mid.link = root
        root = mid
        mid = fore
4

it seems your solution uses two pointers and that’s where the problem is.

You can use three pointers: previousNode,currentNode, and nextNode.

The logic for this would be:

  • Have three nodes i.e previousNode,currentNode and nextNode.
  • When currentNode is starting node, then previousNode will be null
  • AssigncurrentNode.next to previousNode to reverse the link.
  • In each iteration move currentNode and previousNode by 1 node.

Here is the code:

public static Node reverseLinkedList(Node currentNode)
{
	// For first node, previousNode will be null
	Node previousNode=null;
	Node nextNode;
	while(currentNode!=null)
	{
		nextNode=currentNode.next;
		// reversing the link
		currentNode.next=previousNode;
		// moving currentNode and previousNode by 1 node
		previousNode=currentNode;
		currentNode=nextNode;
	}
	return previousNode;
}

Source: Reverse linked list in java