A Singly Linked List is a one-direction List that uses a pointer to connect between Nodes. To reverse a linked list, you need to re-connect the directions, for example:
A --> B --> C becomes A <-- B < -- C
In C/C++, the Singly Linked List can be defined by using structure-type.
1 2 3 4 5 6 7 8 | /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ |
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/Top-Down Recursion
We can divide the Linked List by two parts, the current node and the remainder. We then need to reconnect the remainder to the current node. If we define a helper function that takes a parameter to store the previous node, then we can have a tail recursion implementation like the following. Remember a tail recursion is the recursion function that the only recursive call is the last operation in the function.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | class Solution { public: ListNode* reverseList(ListNode* head, ListNode *prev) { if (head == NULL) { return prev; } ListNode* rem = head->next; head->next = prev; return reverseList(rem, head); } ListNode* reverseList(ListNode* head) { return reverseList(head, NULL); } }; |
class Solution {
public:
ListNode* reverseList(ListNode* head, ListNode *prev) {
if (head == NULL) {
return prev;
}
ListNode* rem = head->next;
head->next = prev;
return reverseList(rem, head);
}
ListNode* reverseList(ListNode* head) {
return reverseList(head, NULL);
}
};Iterative
We can turn above Top-Down approach into a iterative implementation, using the same idea.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | class Solution { public: ListNode* reverseList(ListNode* head) { ListNode *rem; ListNode *prev = NULL; while (head) { rem = head->next; // remainder head->next = prev; // reconnects prev = head; head = rem; // head = remainder } return prev; } }; |
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *rem;
ListNode *prev = NULL;
while (head) {
rem = head->next; // remainder
head->next = prev; // reconnects
prev = head;
head = rem; // head = remainder
}
return prev;
}
};Recursion (bottom up)
The bottom-up recursion solves the problem slightly differently. The recursion will be calling itself until it reaches the end of the list. Then it will be reconnecting the nodes from the end backwards (unrolling). It is not easy to convert this approach to iterative implementation unless you have a Stack structure to manually simulate the recursion.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | class Solution { public: ListNode* reverseList(ListNode* head) { if (head == NULL) { return NULL; } if (head->next == NULL) { return head; } ListNode* x = reverseList(head->next); head->next->next = head; // reverse the direction head->next = NULL; return x; } }; |
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == NULL) {
return NULL;
}
if (head->next == NULL) {
return head;
}
ListNode* x = reverseList(head->next);
head->next->next = head; // reverse the direction
head->next = NULL;
return x;
}
};To reverse a linked list in Javascript, you may refer to this post: How to Reverse a Linked List in Javascript?
See also: Teaching Kids Programming – Reverse a Linked List using Recursion and Iterative Algorithms
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: C++ Coding Exercise - Gas Station
Next Post: How to Delete a Node from a Binary Search Tree?
