java 单链表反转递归法遍历法

左手的ㄟ右手 2022-05-08 09:03 181阅读 0赞

以下是一个例子

package com.haha.demo.util;
    
    public class node {
    
    	static class Node {
    		Integer data;
    		Node next;
    	}
    
    	static Node readyNode() {
    		Node linkNode1 = new Node();
    		linkNode1.data = 1;
    		Node linkNode2 = new Node();
    		linkNode2.data = 2;
    		Node linkNode3 = new Node();
    		linkNode3.data = 3;
    		Node linkNode4 = new Node();
    		linkNode4.data = 4;
    		Node linkNode5 = new Node();
    		linkNode5.data = 5;
    		Node linkNode6 = new Node();
    		linkNode6.data = 6;
    		linkNode1.next = linkNode2;
    		linkNode2.next = linkNode3;
    		linkNode3.next = linkNode4;
    		linkNode4.next = linkNode5;
    		linkNode5.next = linkNode6;
    		return linkNode1;
    	}
    
    	/**
    	 * 递归法单链表反转
    	 * @param node
    	 * @return
    	 */
    	static Node reverseLinkedList(Node node) {
    		if (node == null || node.next == null) {
    			return node;
    		} else {
    			Node headNode = reverseLinkedList(node.next);
    			node.next.next = node;
    			node.next = null;
    			return headNode;
    		}
    	}
    
    	/**
    	 * 遍历法单链表反转
    	 * @param node
    	 * @return
    	 */
    	static Node reverseBlLinkedList(Node node) {
    		Node previousNode = null; //前驱节点
    		Node currentNode = node;  //当前节点
    		Node headNode = null;
    		while (currentNode != null) {
    			Node nextNode = currentNode.next;
    			if (nextNode == null) {
    				headNode = currentNode;
    			}
    			currentNode.next = previousNode;
    			previousNode = currentNode;
    			currentNode = nextNode;
    		}
    		return headNode;
    	}
    
    	public static void main(String [] args){
    		//顺序法链表反转
    		Node kk = readyNode();
    		Node gg = reverseBlLinkedList(kk);
    		System.out.println("反转完毕");
    
    
    		//递归法链表反转
    //		Node kk = readyNode();
    //		Node gg = reverseLinkedList(kk);
    //		System.out.println(12312);
    	}
    
    
    
    }