要求很简单，输入一个链表，反转链表后，输出新链表的表头。反转链表是有2种方法(递归法，遍历法)实现的，面试官最爱考察的算法无非是斐波那契数列和单链表反转，递归方法实现链表反转比较优雅，但是对于不了解递归的同学来说还是有理解难度的。
总体来说，递归法是从最后一个Node开始，在弹栈的过程中将指针顺序置换的。递归法实现图
为了方便理解，我们以 1->2->3->4这个链表来做演示。输出的效果是4->3->2->1
首先定义Node：
package cn.liuhaihua;public class Node<T> {Node next;T object;/* 构造函数* @param next* @param object*/public Node(Node next,T object){this.next=next;this.object=object;}}
反转方法如下：
/* 递归反转* @param node* @return*/public static Node reverse(Node node){Node newnode =null;if(null==node||null==node.next){return node;}else{Node temp = node.next;newnode = reverse(node.next);temp.next = node;node.next=null;}print(newnode);return newnode;}
递归实质上就是系统帮你压栈的过程，系统在压栈的时候会保留现场。
我们来看是怎样的一个递归过程：1->2->3->4
程序到达Node newnode = reverse(node.next);时进入递归 我们假设此时递归到了3结点，此时node=3结点，temp=3结点.next(实际上是4结点) 执行Node newnode = reverse(node.next);传入的node.next是4结点，返回的newnode是4结点。接下来就是弹栈过程了 程序继续执行 temp.next = node就相当于4->3 node.next = null 即把3结点指向4结点的指针断掉。返回新链表的头结点newnode
注意：当return后，系统会恢复2结点压栈时的现场，此时的node=2结点；temp=2结点.next(3结点)，再进行上述的操作。最后完成整个链表的翻转。
遍历法就是在链表遍历的过程中将指针顺序置换
public static Node reverseList(Node node) {Node pre = null;Node next = null;while (node != null) {next = node.next;node.next = pre;pre = node;node = next;}return pre;}
依旧是1->2->3->4 准备两个空结点 pre用来保存先前结点、next用来做临时变量 在头结点node遍历的时候此时为1结点 next = 1结点.next(2结点) 1结点.next=pre(null) pre = 1结点 node = 2结点 进行下一次循环node=2结点 next = 2结点.next(3结点) 2结点.next=pre(1结点)=>即完成2->1 pre = 2结点 node = 3结点 进行循环...
package cn.liuhaihua;/*单链表反序*/public class NodeReverse {public static void main(String args[]){Node<String> node_d = new Node<String>(null,"D");Node<String> node_c = new Node<String>(node_d,"C");Node<String> node_b = new Node<String>(node_c,"B");Node<String> node_a = new Node<String>(node_b,"A");System.out.println("反转前：");print(node_a);System.out.println("反转ing：");//Node reversenode =reverse(node_a);Node reversenode = reverseList(node_a);System.out.println("反转后：");print(reversenode);}/* 递归反转* @param node* @return*/public static Node reverse(Node node){Node newnode =null;if(null==node||null==node.next){return node;}else{Node temp = node.next;newnode = reverse(node.next);temp.next = node;node.next=null;}print(newnode);return newnode;}/* 遍历反转* @param node* @return*/public static Node reverseList(Node node) {Node pre = null;Node next = null;while (node != null) {next = node.next;node.next = pre;pre = node;node = next;print(pre);}return pre;}/* 遍历节点数据* @param node*/public static void print(Node node){System.out.print("node遍历："+node.object.toString());while(node.next!=null){node = node.next;System.out.print("-->"+node.object.toString());}System.out.println("\n");}}
目前+人已关注加入我们
版权声明：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！
转载请注明出处，原文链接：https://www.xkablog.com/qkl-jc/37215.html