1. 题目描述
定义一个函数,输入一个链表的头结点,反转该链表并输出反转后链表的头结点。
2. 思路描述
思路一:经典的“链表头插法”,时间复杂度是 $O(N)$,但是空间复杂度也是 $O(N)$
思路二:链表原地操作,时间复杂度是 $O(N)$,但是空间复杂度只有 $O(1)$。
- 保存当前节点
node
的上一个节点pre
- 节点
node
的next
指向pre
- 分别将
pre
和node
向后移动 1 个位置
- 如果
node
为 null,链表翻转完毕,此时pre
指向新的头节点,返回即可
- 否则,回到第 1 步继续执行
3. 代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
|
class Node { constructor(value, next) { this.value = value this.next = next } }
function reverseList(head) { let node = head, pre = null
while (node) { let next = node.next
node.next = pre
pre = node node = next }
return pre }
let node3 = new Node(3, null), node2 = new Node(2, node3), node1 = new Node(1, node2), head = new Node(0, node1)
let newHead = reverseList(head) while (newHead) { console.log(newHead) newHead = newHead.next }
|