反转一个单链表
输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
在遍历的时候把节点存在数组里面,可以利用reverse
方法,也可以利用数组存储特点做顺序记录
/**
* @param {ListNode} head
* @return {ListNode}
*/
function reverseList(head) {
if (!head) return head;
let list = [],tempNode = null, curNode = head;
while (curNode) {
tempNode = curNode.next || null
curNode.next = list[list.length - 1] || null
list.push(curNode);
curNode = tempNode
}
return list[list.length-1]
};
构建两个指针prev
和cur
分别存储上一个节点和当前节点,然后每次遍历的时候往后挪动两个指针,同时修改prev
和cur
的next
指向
/**
* @param {ListNode} head
* @return {ListNode}
*/
function reverseList(head) {
let prev = null;
let cur = head;
let temp;
while (cur) {
temp = cur.next;
cur.next = prev;
prev = cur;
cur = temp;
}
return prev;
};
这道题使用递归的方法理解会比较绕,结合递归的执行栈
① —-> ② —-> ③ —-> ④ —-> ⑤ —-> null
当前节点 | 返回节点 | 链表 |
---|---|---|
④ | ⑤ | ⑤ --> ④ --> null |
③ | ⑤ | ⑤ --> ④ --> ③ --> null |
② | ⑤ | ⑤ --> ④ --> ③ --> ② --> null |
① | ⑤ | ⑤ --> ④ --> ③ --> ② --> ① --> null |
function reverseList(head) {
if (!head || !head.next) return head;
let nextLoopStartNode = reverseList(head.next);
// 原本关系:headPrev = null, headNext = head.next
// 反转操作:head.next = null, headNext.next = head
head.next.next = head;
head.next = null;
return nextLoopStartNode;
}