How to Reverse a Linked List in Javascript?
- 时间:2020-09-17 10:57:36
- 分类:网络文摘
- 阅读:76 次
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) —
推荐阅读:威廉·向克斯的憾事 由掷骰子引起的争论 生日相同的五个同胞姐弟 负数的引入 数学童话故事连载(一)作者简介及前言 数学童话故事连载(二)夜半狼嚎 数学童话故事连载(三)狼王应考 数学童话故事连载(四)烂瓜砸头 偶然的巧遇——迪卡尔的故事 女生有多少人
- 评论列表
-
- 添加评论