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) —
推荐阅读:上海东方明珠塔作文400字 冬日趣事作文100字 妈妈母亲节快乐作文300字 光辉的转折作文900字 金钟水库作文400字 三下乡之山雨欲来无征兆 擀面皮作文450字 元旦节的作文200字 最大公因数是6,最小公倍数是90 3a+2b=54,2a+3b=56,求 ab 的值?
- 评论列表
-
- 添加评论