2020小米算法面试（miui组） java 实现链表反向

落日映苍穹つ 2022-06-14 05:49 130阅读 0赞

最近有很多面试者在群里面问我，算法怎么实现链表的反转。

所以我写了个demo 实现它，代码可以直接运行并且是一定能够执行的（这是博主一贯的作风，因为现在有很多博客写的都是错的那还有什么参考的价值呢？），下面是代码部分：

package test;
    
    /**
     * java 实现链表反向demo
     * csdn 博客地址:http://blog.csdn.net/sai739295732
     * @author saicy
     */
    public class test {
    	class Node{
    		private int data;
    		private Node next;
    		public int getData() {
    			return data;
    		}
    		public void setData(int data) {
    			this.data = data;
    		}
    		public Node getNext() {
    			return next;
    		}
    		public void setNext(Node next) {
    			this.next = next;
    		}
    		@Override
    		public String toString() {
    			return "Node [data=" + data + ", next=" + next + "]";
    		}
    		
    	}
    	
    	public static void main(String[] args) {
    		test t = new test();
    		test.Node node1 = t.new Node();
    		test.Node node2 = t.new Node();
    		test.Node node3 = t.new Node();
    		node1.setData(1);
    		node2.setData(2);
    		node3.setData(3);
    		node1.setNext(node2);
    		node2.setNext(node3);
    		System.out.println("反转前输出前数据");
    		printNodeList(node1);
    		//反转方法
    		Node returnNode = reserverNodeList(node1);
    		System.out.println("反转后输出后数据");
    		printNodeList(returnNode);
    	}
    	//核心原理是对对象的引用进行操作
    	//反转链表
    	private static Node reserverNodeList(Node node){
    		Node returnNode = null;
    		while(node !=null){
    			Node preNode = node.getNext();
    			node.setNext(returnNode);
    			returnNode = node;
    			node = preNode;
    		}
    		return returnNode;
    	}
    	//输出链表的值
    	private static void printNodeList(Node node){
    		StringBuilder str = new StringBuilder();
    		while (node != null){
    			str.append(node.getData()+" ");
    			node = node.getNext();
    		}
    		System.out.println(str.toString());
    	}
    }

测试的结果输出：

![Center][]

总结：核心是两个节点链表相互拷贝（一个链表中的引用地址提取出来反向拷贝到宁外一个链表中。谢谢大家的支持，支持原创，成为真正的强者。

[Center]: /images/20220614/f3d80a62a68643c99eae20ea6a346515.png