将链表反转,即将每个表元的指针从向后变成向前,那我们可以遍历原始链表,将遇到的节点一一指针逆向即可。
step 1:优先处理空链表,空链表不需要反转。 step 2:我们可以设置两个指针,一个当前节点的指针,一个上一个节点的指针(初始为空)。 step 3:遍历整个链表,每到一个节点,断开当前节点与后面节点的指针,并用临时变量记录后一个节点,然后当前节点指向上一个节点,即可以将指针逆向。 step 4:再轮换当前指针与上一个指针,让它们进入下一个节点及下一个节点的前序节点。
方法二:正规解法 但是面试的时候,上一种解法当然不行。此题想考察的是:如何调整链表指针,来达到反转链表的目的。 初始化:3个指针
- pre指针指向已经反转好的链表的最后一个节点,最开始没有反转,所以指向nullptr
- cur指针指向待反转链表的第一个节点,最开始第一个节点待反转,所以指向head
- nex指针指向待反转链表的第二个节点,目的是保存链表,因为cur改变指向后,后面的链表则失效了,所以需要保存
接下来,循环执行以下三个操作
- nex = cur->next, 保存作用
- cur->next = pre 未反转链表的第一个节点的下个指针指向已反转链表的最后一个节点
- pre = cur, cur = nex; 指针后移,操作下一个未反转链表的第一个节点 循环条件,当然是cur != nullptr 循环结束后,cur当然为nullptr,所以返回pre,即为反转后的头结点 这里以1->2->3->4->5 举例:
/*function ListNode(x){
this.val = x;
this.next = null;
}*/
function ReverseList(pHead)
{
console.log(pHead)
if(pHead == null || pHead.next == null){
return pHead;
}
let p1 = null, p2 =null;
while(pHead !== null){
//1次 1=>2=>3=>null
//2次 2=>3=>null
//1次 2=>3=>null
//2次 3=>null
p1 = pHead.next;
//1次 1=>null
//2次 2=>1=>null
pHead.next = p2;
//1次 1=>null
//2次 2=>1=>null
p2 = pHead;
pHead = p1;
}
return p2;
}
module.exports = {
ReverseList : ReverseList
};