尾插法实现单链表的创建、递归实现链表的反转

     一、什么是链表

 我们一般用数组来表示的一窜数据。那我们是通过数组来存入数据呢。这个大家都知道-->就是通过下标的形式。（从下标0依次往下添加）。

      而链表就没有下标这种概念。它是可以说是一个节点模型。一个节点模型一般包括我们想要存放的<T> value（比如数组里面的一个一个的数字）和指向下一个Node节点的next(next-->指向下一个节点)。

    节点模型所需要的value和指向下一个next这些属性我们可以创建在一个Node类里，这样其他类想要调用的时候，可以实例这个Node类，这个类可以写成这样。就一个我们想存放的值和指向下一个节点的next并且设置了get，set，toString方法（这里用到了泛型，如果想直接用数字的话，就把泛型设置成Integer就好了，我这里是方便存放其他类的对象）。

public class Node<T> { private T t; private Node<T> next; public T getT() { return t; } public void setT(T t) { this.t = t; } public Node<T> getNext() { return next; } @Override public String toString() { return "Node{" + "t=" + t + ", next=" + next + '}'; } }

   如果我想把1,11,12,13,14，存在这个存放在一个链表里面，

  1、首先我们先创建一个Node节点。    比如：Node node1=new Node()；node1.setT(1);这些代码就会在jvm堆里面创建node1的地址。并给属性t复制1.(如图，jvm会在栈里面创建一个node1变量，在堆里面创建node1的地址，并让node1指向这个地址)

2、然后我们在创建一个Node节点，存放下一个数字，并让上一个节点的next的指针（伪指针，java中是没有指针的。）指向这个节点。比如这些代码：Node node2=new Node()；node2.setT(11);node2.setNext(node1);。这三行代码分别作了。在栈创建了一个node2的对象，在堆中创建了这个对象的地址。node2指向这个堆的地址。然后给这个堆中的属性t赋值11.最后让上一个node1的next节点指向node2。

如上图：此时node1就是一个链表。这个链表有俩个数据，1和11.输出node1的具体形式大概就是：{t=1, next=Node{t=11, next=null}}.这样的。

3、如果我们接着还想往这个链表插入数据。类似步骤2.创建新节点，给新节点赋值，在让上一个节点指向这个新创建的节点就好了。然后node1就是成为了：{t=1, next=Node{t=11, next=Node{t=12, next=null}}}.以此不断创建不断插入进去。这就是链表。

二、单链表的创建

刚刚了解链表的大概行程过程，那我们怎么实现想java那样add();添加呢。这里就在写一个Link类。在这个类写add（）方法。

public class Link<T> { private Node<T> head=null; public void add(T te){ Node<T> tNode = new Node<T>(); if (head==null){ tNode.setT(te); head=tNode; }else { Node<T> text = head; while (text.getNext()!=null){ text=text.getNext(); } tNode.setT(te); text.setNext(tNode); } } }

写一个Link类，声明一个Node类的属性head，默认为空。刚开始插入的时候，如果head为null。就往head里面插入。如果不为null，就做一个循环。找到head.getNdext()为空的那个节点。然后对那个节点设置next指向就好了。

这里需要需要注意一下。循环查找head.在第几个节点为null时。千万别写成:

while (head.getNext()!=null){ head=head.getNext(); }

这样会导致head直接指向head这个链表的最后一个节点。前面的节点就会丢失。（是真的，作者亲自踩过这个坑。）所以最好先用text=head。用text去做判断，赋值。不用担心text会怎么样。因为方法执行完毕之后text这个变量也会被回收的。然而text会帮head设置好最后节点的next节点。

这里我们main方法测试一下：

public class text { public static void main(String[] args) { Link<Integer> integerLink = new Link<Integer>(); for (int i = 0; i < 10; i++) { integerLink.add(i); } System.out.println(integerLink); } }

测试结果（这里由于Link类我没有写输入的方法。我就用debug给大家展示了）：

可以很明显的看出这个Node是{t=0, next=Node{t=1, next=Node{t=2, next=Node{t=3, next=Node{t=4, next=Node{t=5, next=Node{t=6, next=Node{t=7, next=Node{t=8, next=Node{t=9, next=null}}}}}}}}}}的链表形式

 

三、递归实现链表的反转

是使用递归实现的。方法一直递归调用但是又不执行完毕。直到找到该链表的最后一个节点。将最后一个节点放在开头（这里创建一个新Node对象存放。）然后放置好最后一个值红，最后一个方法判断该方法执行完毕。然后出栈。执行倒数第二个方法。将倒数第二个方法想放置的数放在新链表的第二位置红判断该方法执行完毕。然后出栈。以此递归。

具体代码：在Node类中写入

public Node<T> newNode(Node<T> linkNode){ if (linkNode==null||linkNode.getNext()==null){ return linkNode; } Node<T> temp=linkNode.getNext(); Node<T> newNode = newNode(linkNode.getNext()); temp.setNext(linkNode); linkNode.setNext(null); return newNode; }

main方法测试一下：

public class text { public static void main(String[] args) { Node<Integer> node1=new Node<Integer>(); Node<Integer> node2=new Node<Integer>(); Node<Integer> node3=new Node<Integer>(); Node<Integer> node4=new Node<Integer>(); Node<Integer> node5=new Node<Integer>(); node1.setT(1); node2.setT(2); node3.setT(3); node4.setT(4); node5.setT(5); node1.setNext(node2); node2.setNext(node3); node3.setNext(node4); node4.setNext(node5); System.out.println("反转前："+node1); Node<Integer> integerNode1 = new Node<Integer>(); Node<Integer> integerNode = integerNode1.newNode(node1); System.out.println("反转后："+integerNode); } }

测试结果：

 

关于链表：它指针密切相关。我们必须理解到指针的类型、指针所指向的类型、指针的值即指针所指向的内存区、还有指针本身所占据的内存区的程度就可以了。要不很容易会在创建的时候指错地址。