- Notifications
You must be signed in to change notification settings - Fork24
Open
Labels
Description
迭代
1.初始化哨兵节点 prev 为 null，及当前节点 curr 指向头节点。
2.开始迭代，记录 next 指针留备后用，反转指针。
3.推进指针继续迭代，最后返回新的链表头节点 prev。
constreverseList=function(head){letprev=null;letcurr=head;while(curr!==null){// 记录 next 节点letnext=curr.next;// 反转指针curr.next=prev;// 推进指针prev=curr;curr=next;}// 返回翻转后的头节点returnprev;};
- 时间复杂度: O(n)
- 空间复杂度: O(1)
递归
constreverseList=function(head){if(!head||!head.next)returnhead;// 记录当前节点的下一个节点letnext=head.next;letreverseHead=reverseList(next);// 操作指针进行反转head.next=null;next.next=head;returnreverseHead;};
- 时间复杂度: O(n)
- 空间复杂度: O(n)