How to Reverse a Linked List in Javascript?
- Time:2020-09-17 10:57:36
- Class:Weblog
- Read:23
Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL
Output: 5->->->2->1->NULL
Follow up:A linked list can be reversed either iteratively or recursively. Could you implement both?
Reversing a linked list (an the data structure of a linked list itself) is not an essential technique you would need to master during your daily work life. However, it is a quite popular interview question (being asked in candidate screenings)
Generally speaking, to reverse a linked list, you can do this in recursion or iteratively.
Recursively Reverse a Linked List
To solve this problem recursively, we have to think recursively. First, we can split the linked list into two halves. The nodes that have been reversed and the remaining linked list that are yet to reverse.
Then, for current node, we have to reverse its directions, by reverse pointing its next node (to itself) and point current node to NULL (delete the original link).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | /** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {ListNode} */ var reverseList = function(head) { if (!head) return null; if (!head.next) return head; let rev = reverseList(head.next); head.next.next = head; head.next = null; return rev; }; |
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {ListNode} */ var reverseList = function(head) { if (!head) return null; if (!head.next) return head; let rev = reverseList(head.next); head.next.next = head; head.next = null; return rev; };
Iteratively Reverting a Linked List
By iteration, the algorithm to reverse a linked list is much easier to understand. We need to maintain a previous node (which is set to NULL at the beginning). Then, as we move forwards along the linked list, we point current node’s direction to the previous node, then we move one node until the end (updating the previous node, current node).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | /** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {ListNode} */ var reverseList = function(head) { let prev = null; while (head) { let p = head.next; head.next = prev; prev = head; head = p; } return prev; }; |
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {ListNode} */ var reverseList = function(head) { let prev = null; while (head) { let p = head.next; head.next = prev; prev = head; head = p; } return prev; };
To Reverse a linked list using Top-Bottom Recursion, Bottom-Up Recursion or Iterative Approach in C++, you can refer to this post: How to Reverse a Linked List in C/C++?
–EOF (The Ultimate Computing & Technology Blog) —
Recommend:4 Frequently Discussed SEO Myths Exposed
3 Reasons Why Graphic Designers Need to Self-Promote through Ins
How to Split a String in C++?
The Best Instagram Feed WordPress Plugins to Use
Trie Class Data Structure in Python
How to Monitor the CPU Temperature of Raspberry PI using Python
Listen to what an SEO expert has to say about its benefits
Depth First Search Algorithm to Compute the Smallest String Star
Algorithm to Check if All Points are On the Same Line
Prefix Sum Algorithm to Count Number of Nice Subarrays
- Comment list
-
- Comment add