带你秒懂递归AND非递归反转单链表
今天偶然看到春招面经中有人说道反转单链表,话说翻转单链表真的是面试官非常喜欢问的问题。于是乎打开eclipse,沉思沉思。。。。。。最后整理出了递归及非递归两种方法翻转单链表,如有错误请纠正。
非递归:
总体思想是新建一个头节点并置初值为null(可将其理解为创建了一个新链表),然后将原链表中的元素逐个添加到新链表中,并将新添加的节点作为新头节点。因此,原链表中的最后一个节点便成了新链表中的头结点。
。。。。。。。。。。。。。。。。。。。。。。。。。
。。。。。。。。。。。。。。。。。。。。。。。。。
贴上代码:
链表中的节点:
进行非递归翻转操作:
递归:
总体思想是遍历链表,从链表倒数第二个节点开始,让节点指向的下一个节点的下一个节点指向自身(node.next.next=node),然后将当前节点的下一节点置空(node.next=null),重复操作直至到头节点也操作完成后停止。
。。。。。。。。。。。。。。。。。。。。。。。。。。。。
。。。。。。。。。。。。。。。。。。。。。。。。。。。。
贴上代码:
链表中的节点依旧如上:
进行递归翻转操作:
总结:
总的来说非递归比递归更好理解,翻转链表应当是比较基础的一个问题,希望各位都能理解透彻咯。