• 欢迎光临~

反转链表

开发技术 开发技术 2022-07-20 次浏览

描述

  给定一个单链表的头结点pHead(该头节点是有值的,比如在下图,它的val是1),长度为n,反转该链表后,返回新链表的表头。 
  数据范围: 0leq nleq10000n1000
  要求:空间复杂度 O(1)O(1) ,时间复杂度 O(n)O(n) 。
 
 如当输入链表{1,2,3}时,
 经反转后,原链表变为{3,2,1},所以对应的输出为{3,2,1}。
 以上转换过程如下图所示:  
              反转链表

示例1

输入:{1,2,3}

输出:{3,2,1}

示例2

输入:{ }

返回值:{ }

说明:空链表则输出空

 

function ReverseList(pHead){

if(pHead == null || pHead.next == null){     // 判断链表为空或长度为1的情况
return pHead;
}
let p1 = null,
p2 = null;                    //创建两个空指针
while(pHead!=null){
p1 = pHead.next          // p1: 2->3->null
pHead.next = p2             // pHead: 1->null p1 指针指向pHead 后面的链表,可以当做标记存储
p2 = pHead               // p2: 1->null p2 指针用来创建新的反转链表。
// pHead: 2->3->null
pHead = p1
}
return p2        // write code here

}
module.exports = {
ReverseList : ReverseList
};

相关内容:

反转链表

 

反转链表

 

 反转链表

 

 

 

 

 

 

 

 

程序员灯塔
转载请注明原文链接:反转链表
喜欢 (0)