Knowing how to work with the C++ programming language makes you a competitive candidate for various roles. As you break into new roles, youβll advance through interviews that test your understanding of computer science fundamentals such as data structures and algorithms. A linked list is just one of many C++ data structures you need to know for interviews. One popular interview question is reversing a linked list.
Today, weβll cover a tutorial on reversing singly linked lists in C++. Weβll demonstrate an iterative and recursive solution to this problem.
Weβll cover:
- Linked lists
- Problem description: Reversing a linked list
- Solution 1: Reverse a linked list using iteration
- Solution 2: Reverse a linked list using recursion
- Wrapping up and next steps
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.
#include<bits/stdc++.h>
using namespace std;
struct node {
int data;
struct node *next;
};
// We construct a linked list and use this function to push elements to the list
void push(struct node **head_ref, int data) {
struct node *node;
node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->next = (*head_ref);
(*head_ref) = node;
}
// Function to reverse the list
void reverse(struct node **head_ref) {
struct node *temp = NULL;
struct node *prev = NULL;
struct node *current = (*head_ref);
while(current != NULL) {
temp = current->next;
current->next = prev;
prev = current;
current = temp;
}
(*head_ref) = prev;
}
// Checking our program
void printnodes(struct node *head) {
while(head != NULL) {
cout<<head->data<<" ";
head = head->next;
}
}
// Driver function
int main() {
struct node *head = NULL;
push(&head, 28);
push(&head, 21);
push(&head, 14);
push(&head, 7);
cout << "Original Linked List" << endl;
printnodes(head);
reverse(&head);
cout << endl;
cout << "Reversed Linked List"<<endl;
printnodes(head);
return 0;
}
==>Original Linked List
==>7 14 21 28
==>Reversed Linked List
==>28 21 14 7
O(N) is the time complexity of this solution since we iterate through each element at least once. O(1) is the space complexity because no extra memory was needed for the solution.
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.
#include<bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
Node(int data)
{
this->data = data;
next = NULL;
}
};
struct LinkedList {
Node* head;
LinkedList()
{
head = NULL;
}
Node* reverse(Node* head)
{
if (head == NULL || head->next == NULL)
return head;
// Recursive call
Node* rest = reverse(head->next);
head->next->next = head;
head->next = NULL;
return rest;
}
void print()
{
struct Node* temp = head;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
}
void push(int data)
{
Node* temp = new Node(data);
temp->next = head;
head = temp;
}
};
int main()
{
LinkedList ll;
ll.push(28);
ll.push(21);
ll.push(14);
ll.push(7);
cout << "Original Linked List\n";
ll.print();
ll.head = ll.reverse(ll.head);
cout << "\nReversed Linked List \n";
ll.print();
return 0;
}
==>Original Linked List
==>7 14 21 28
==>Reversed Linked List
==>28 21 14 7
The space complexity of this solution is O(N) since we create a recursive stack for each recursive function call. O(N) is the time complexity of this solution, since we iterate through each element at least once.
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
- 9 C++ data structures you need to know for your interview
Start a discussion
How do you approach reversing linked lists? Is there anything we missed that you'd like to learn about? Let us know in the comments below!
Top comments (0)