Tutorial: How To Reverse A Linked List In C++

Linked lists#

Linked lists are linear data structures connecting nodes in a sequence. Each node has two components: 1.) A data element and 2.) A pointer containing a memory address to the next node in the list.

In the case of a singly linked list, nodes only store one pointer to the next node in the sequence. A node in a doubly linked list, on the other hand, stores two pointers: one to the next node, and one to the previous node in the sequence. A singly linked list is uni-directional while a doubly linked list is bi-directional. In the case of a singly linked list, the tail node’s pointer is null.

Some terms associated with linked lists are:

• Node: The object in the list, with two components: a piece of data (element) and a pointer.
• Next: The next node in a sequence, respective to a given list node
• Head: The first node in a linked list
• Tail: The last node in a linked list is called the tail.
• Head pointer: The memory address contained by the head node referencing the first node in the list

Linked lists may be the second most used data structure, behind arrays. Linked lists are great for quickly adding and deleting nodes. They can be used to implement stacks and queues, as well as other abstract data types. Linked lists are often used to maintain directories of names, or for dynamic memory allocation.

Problem description: Reversing a linked list#

We’re provided the pointer or reference to the head node of a singly linked list. We must sequence the list in reverse order and return the pointer to the head of the reversed linked list. The head of the original linked list becomes the tail of the reversed linked list, and the tail of the original linked list becomes the head of the reversed linked list.

For example, provided the given linked list:

The reversed linked list would look like this:

Solution 1: Reverse a linked list using iteration#

If the linked list has two or more elements, we can use three pointers to implement an iterative solution. We use a function to reverse the linked list. Passing the head pointer as the sole argument, the function will return the head of the reversed list.

We’ll define three nodes: current (with reference to the head node), and temp and prev (with null pointers). Using a while loop, we traverse the linked list until the next pointer does not yield null.

In the iterative process, we’ll perform these operations:

• temp = current->next;
  • Assigns temp node to the current node’s next node
• current->next = prev;
  • Assigns current node to the previous node’s next node
• prev = current;
  • Increments previous node to current node
• current = temp;
  • Increments current node to temp node

We then return the reversed list’s head node.

Solution 2: Reverse a linked list using recursion#

The recursive solution uses a stack. Each recursive call requires your compiler to allocate stack memory. Since recursive implementation can run out of memory, the recursive solution isn’t the best approach when working with very large linked lists.

To return the head of the new list, we recursively visit each node in the given linked list until we reach the last node. This last node then serves as the new head of the list. On the return path, each node appends itself to the end of the partial reversed list.

Wrapping up and next steps#

Now you know how to reverse a linked list! This is a common question in C++ coding interviews. Before going to a coding interview, you’ll want to be comfortable with as many C++ data structures as possible.

To help you learn C++, check out our Ace the C++ Coding Interview learning path. This interactive learning path helps you prepare for C++ interviews with several modules and quizzes, including content covering several other operations on data structures.

Happy learning!

Continue learning about C++#

• How to pass an array to a function in C++
• Intermediate C++ tutorial: Strings, maps, memory, and more
• What is Vector in C++? Get started in 5 minutes
• Learn C++ from scratch: The complete guide for beginners

You should reverse a linked list by modifying the node connections. Start from a given pointer to the list’s head node. This should be accomplished using a recursive approach.