一、题目描述
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
限制
0 <= 节点个数 <= 5000
二、题目解析
- 遍历法
遍历该链表，用一个结果数组来逆序保存遍历到的链表元素，再根据数组生成逆序的链表。
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
let current = head;
const result = [];
while(current != null) {
result.unshift(current.val);
current = current.next;
}
const resultHead = new ListNode(null);
current = resultHead;
for(let i = 0;i < result.length;i ++) {
current.next = new ListNode(result[i]);
current = current.next;
}
return resultHead.next;
};
- 时间复杂度:
O(n),n为链表长度 - 空间复杂度:
O(n)，n为链表长度
- 双指针法
定义prev,current两个指针，刚开始prev指向null,current指向head。然后开始对链表进行遍历，每次遍历先用temp
保存current.next，然后让current的下一个节点指向prev，直至current为null，此时的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, current = head;
while(current != null) {
const temp = current.next;
current.next = prev;
prev = current;
current = temp;
}
return prev;
};
- 时间复杂度:
O(n),n为链表长度 - 空间负责度:
O(1)，prev,head仅使用常量级别的存储空间