反转单向链表
以Java语言为主,实现如下:
publicclassNode{ publicintvalue; publicNodenext; publicNode(intvalue){ this.value=value; } publicNodereverseList(Nodehead){ Nodeprev=null;//用于暂存前面的节点 Nodenext=null;//用于暂存后面的节点 while(head!=null){ next=head.next;//把后面的节点暂存起来 head.next=prev;//当前节点的next就可以指向暂存的上一个节点,也即,反转节点指向 prev=head;//把当前节点设置为上一个节点 head=next;//设置下一个节点为当前节点 } returnprev; } }
该方法的时间复杂度是O(n),空间复杂度是O(1)。