数据结构-链表-单向链表
面5笔5一个长度为n的单向链表,用O(1) 空间复杂度来实现倒转输出,使用最低时间复杂度
空间复杂度为O(1),只能一次取一个结点,并把它的next结点指向第一个结点
具体分析,可以从1个结点入手,再到2个结点,3个结点
分析完后,需要4个结点,
1.当前循环结点 q
2.暂存结点p,用来记录q的下一个结点
3. 每次指针重定向后的链表的头结点newHead,也就是每次q.next所指向的结点
4. 原链表头结点head, head.next结点无指向,设为null
Node reverse(Node head)
{
if(head == null || head.next == null){
return head;
}
Node newHead =head; //保持链表的首结点
Node q = newHead.next; Node p;//p是记录结点,先直接定义
while(q != null) {
p =q.next; //保存结点
q.next=newHead;
newHead = q; //记录头指针
q = p; //继续下一个
}
head.next=null;
head=tHead;
return head;
}