206. Reverse Linked List(反转链表)
难度: Easy
刷题内容
原题连接
内容描述
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
解题方案
- 思路1 ：暴力解法
将链表转化为数组，再利用数组重建数组。
思路 - 时间复杂度: O(N²)
- 空间复杂度: O(N)
执行用时 :96 ms, 在所有 JavaScript 提交中击败了54.77%的用户
内存消耗 :35.2 MB, 在所有 JavaScript 提交中击败了30.19%的用户
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
var nodeList = []
if (!head) {
return head
}
while (head.next) {
nodeList.push(head)
head = head.next
}
nodeList.push(head)
nodeList.forEach((node, index) => {
if (nodeList[index - 1]) {
node.next = nodeList[index - 1]
} else {
node.next = null
}
})
return nodeList[nodeList.length - 1]
};
- 思路2： 迭代法
使用parentNode缓存上次循环的结果，每次循环都生成两个新的ListNode用来翻转链表各个元素，一次迭代即可完成链表反转。
思路 - 时间复杂度: O(N)
- 空间复杂度: O(1)
执行用时 :116 ms, 在所有 JavaScript 提交中击败了20.19%的用户
内存消耗 :35.5 MB, 在所有 JavaScript 提交中击败了14.78%的用户
/**
* 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 head
}
let parentNode = null
while (head) {
let current = new ListNode(head.val)
current.next = parentNode
if (head.next) {
let next = new ListNode(head.next.val)
next.next = current
} else {
let next = null
return current
}
parentNode = current
head = head.next
}
return head
};
