链表创建、反转链表 （递归分析）

链表创建

严格定义递归函数作用，包括参数，返回值，side-effect先一般后特殊；每次调用必须缩小问题规模每次问题规模必须缩小1

缩小规模

把1拆掉，建2 3 4 5 的LinkedList ,然后把1 连接上

代码：

public class Node { private final int value; private Node next; public Node(int value){ this.value=value; this.next=null;//构造函数默认指向null } public int getValue() { return value; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; } /** * 打印链表的值 * @param head */ public static void printLinkedList(Node head){ while(head!=null){ System.out.print(head.getValue()); System.out.print(" "); head=head.getNext(); } System.out.println(); } } package testPro; import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class LinkedListCreator { /** * Creates a linked list. * * @param data the data to create the list * @return head of the linked list. The returned linked list * ends with last node with getNext()==null; */ public Node createLinkedList(List<Integer> data){ if(data.isEmpty()){ return null; } Node firstNode=new Node(data.get(0)); Node headOfSublist= createLinkedList(data.subList(1,data.size()));//规模缩小1 firstNode.setNext(headOfSublist);//第一个节点Node指向headOfSublist return firstNode;//head } public static void main(String[] args) { LinkedListCreator creator=new LinkedListCreator(); Node.printLinkedList( creator.createLinkedList(new ArrayList<>())); Node.printLinkedList( creator.createLinkedList(Arrays.asList(1))); Node.printLinkedList( creator.createLinkedList(Arrays.asList(1,2,3,4,5))); } }

反转链表

public class LinkedListNodeReverse { public Node reverseLinkedList(Node head){ if(head ==null|| head.getNext()==null){ return head; } Node newHead = reverseLinkedList(head.getNext());//新的头节点 head.getNext().setNext(head);//head的下一个节点指向head,从而完成反转 head.setNext(null);//完成反转后，head的下一个节点指向null return newHead; } public static void main(String[] args) { LinkedListCreator creator=new LinkedListCreator(); LinkedListNodeReverse reverse=new LinkedListNodeReverse(); Node.printLinkedList(//按照上面的例子，先创建链表再反转 reverse.reverseLinkedList( creator.createLinkedList(new ArrayList<>()))); Node.printLinkedList( reverse.reverseLinkedList( creator.createLinkedList(Arrays.asList(1)))); Node.printLinkedList( reverse.reverseLinkedList( creator.createLinkedList(Arrays.asList(1,2,3,4,5)))); } }