package link.list;

import java.util.Stack;

public class LinkListTest {

讯享网</span><span style="color: rgba(0, 0, 255, 1)">public</span> <span style="color: rgba(0, 0, 255, 1)">static</span> Node head; <span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)">标识单链表的头结点</span> <span style="color: rgba(0, 0, 255, 1)">public</span> <span style="color: rgba(0, 0, 255, 1)">static</span> <span style="color: rgba(0, 0, 255, 1)">void</span><span style="color: rgba(0, 0, 0, 1)"> main(String[] args) { System.out.printf(</span>"创建链表"<span style="color: rgba(0, 0, 0, 1)">); creatList(); </span><span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)"> 链表创建后, 打印链表</span> 

printLinkList(head);

讯享网

 System.out.printf(</span>"开始反转链表"<span style="color: rgba(0, 0, 0, 1)">); </span><span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)"> 反转后打印链表 </span><span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)"> 通过迭代的方式实现 

// Node reverserNode = reverserLinkedList(head);

讯享网 </span><span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)"> 通过栈的方式实现 

// Node reverserNode = reverserLinkByStack(head);

 </span><span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)"> 通过循环的方式实现</span> Node reverserNode =<span style="color: rgba(0, 0, 0, 1)"> reverserLinkByLink(head); printLinkList(reverserNode); } </span><span style="color: rgba(0, 0, 255, 1)">public</span> <span style="color: rgba(0, 0, 255, 1)">static</span> <span style="color: rgba(0, 0, 255, 1)">void</span><span style="color: rgba(0, 0, 0, 1)"> creatList() { Node node1 </span>= <span style="color: rgba(0, 0, 255, 1)">new</span> Node(13<span style="color: rgba(0, 0, 0, 1)">); Node node2 </span>= <span style="color: rgba(0, 0, 255, 1)">new</span> Node(2<span style="color: rgba(0, 0, 0, 1)">); Node node3 </span>= <span style="color: rgba(0, 0, 255, 1)">new</span> Node(5<span style="color: rgba(0, 0, 0, 1)">); node1.next </span>=<span style="color: rgba(0, 0, 0, 1)"> node2; node2.next </span>=<span style="color: rgba(0, 0, 0, 1)"> node3; head </span>=<span style="color: rgba(0, 0, 0, 1)"> node1; } </span><span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)"> 打印链表</span> <span style="color: rgba(0, 0, 255, 1)">public</span> <span style="color: rgba(0, 0, 255, 1)">static</span> <span style="color: rgba(0, 0, 255, 1)">void</span><span style="color: rgba(0, 0, 0, 1)"> printLinkList(Node node) { System.out.println(</span>"开始打印head"<span style="color: rgba(0, 0, 0, 1)">); </span><span style="color: rgba(0, 0, 255, 1)">while</span> (node != <span style="color: rgba(0, 0, 255, 1)">null</span><span style="color: rgba(0, 0, 0, 1)">) { System.out.println(node.data </span>+ ""<span style="color: rgba(0, 0, 0, 1)">); node </span>=<span style="color: rgba(0, 0, 0, 1)"> node.next; } } </span><span style="color: rgba(0, 128, 0, 1)">/</span><span style="color: rgba(0, 128, 0, 1)"> * 递归反转链表 * 这个递归,返回值只是为了控制返回的是最后一个节点 * 然后通过递归, 通过栈的特性, 这里就是让它可以从最后一个节点开始把自己的子节点的子节点改成自己 * 自己子节点改成null * </span><span style="color: rgba(128, 128, 128, 1)">@param</span><span style="color: rgba(0, 128, 0, 1)"> node * </span><span style="color: rgba(128, 128, 128, 1)">@return</span> <span style="color: rgba(0, 128, 0, 1)">*/</span> <span style="color: rgba(0, 0, 255, 1)">public</span> <span style="color: rgba(0, 0, 255, 1)">static</span><span style="color: rgba(0, 0, 0, 1)"> Node reverserLinkedList(Node node) { </span><span style="color: rgba(0, 0, 255, 1)">if</span> (node == <span style="color: rgba(0, 0, 255, 1)">null</span> || node.getNext() == <span style="color: rgba(0, 0, 255, 1)">null</span><span style="color: rgba(0, 0, 0, 1)">) { </span><span style="color: rgba(0, 0, 255, 1)">return</span><span style="color: rgba(0, 0, 0, 1)"> node; } Node nextNode </span>=<span style="color: rgba(0, 0, 0, 1)"> reverserLinkedList(node.getNext()); node.getNext().setNext(node); node.setNext(</span><span style="color: rgba(0, 0, 255, 1)">null</span><span style="color: rgba(0, 0, 0, 1)">); </span><span style="color: rgba(0, 0, 255, 1)">return</span><span style="color: rgba(0, 0, 0, 1)"> nextNode; } </span><span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)"> 使用栈的方式, 把递归变成循环</span> <span style="color: rgba(0, 0, 255, 1)">public</span> <span style="color: rgba(0, 0, 255, 1)">static</span><span style="color: rgba(0, 0, 0, 1)"> Node reverserLinkByStack(Node node) { Stack</span>&lt;Node&gt; nodeStack = <span style="color: rgba(0, 0, 255, 1)">new</span> Stack&lt;&gt;<span style="color: rgba(0, 0, 0, 1)">(); Node head </span>= <span style="color: rgba(0, 0, 255, 1)">null</span><span style="color: rgba(0, 0, 0, 1)">; </span><span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)"> 存入栈中, 模拟递归开始的栈状态</span> <span style="color: rgba(0, 0, 255, 1)">while</span> (node!=<span style="color: rgba(0, 0, 255, 1)">null</span><span style="color: rgba(0, 0, 0, 1)">) { nodeStack.push(node); node </span>=<span style="color: rgba(0, 0, 0, 1)"> node.getNext(); } </span><span style="color: rgba(0, 128, 0, 1)">/*</span><span style="color: rgba(0, 128, 0, 1)"> * 特殊处理第一个栈顶元素(也就是反转前的最后一个元素, 因为它位于最后, 不需要反转, * 如果它参参与下面的while, 因为它的下一个节点为空, 如果getNode(), 会引发空指针) </span><span style="color: rgba(0, 128, 0, 1)">*/</span> <span style="color: rgba(0, 0, 255, 1)">if</span> (!<span style="color: rgba(0, 0, 0, 1)">nodeStack.isEmpty()) { head </span>=<span style="color: rgba(0, 0, 0, 1)"> nodeStack.pop(); } </span><span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)"> 排除以后就可以快乐的循环了</span> <span style="color: rgba(0, 0, 255, 1)">while</span>(!<span style="color: rgba(0, 0, 0, 1)">nodeStack.isEmpty()) { Node tempNode </span>=<span style="color: rgba(0, 0, 0, 1)"> nodeStack.pop(); tempNode.getNext().setNext(tempNode); tempNode.setNext(</span><span style="color: rgba(0, 0, 255, 1)">null</span><span style="color: rgba(0, 0, 0, 1)">); } </span><span style="color: rgba(0, 0, 255, 1)">return</span><span style="color: rgba(0, 0, 0, 1)"> head; } </span><span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)"> 第三种方式反转链表</span> <span style="color: rgba(0, 0, 255, 1)">public</span> <span style="color: rgba(0, 0, 255, 1)">static</span><span style="color: rgba(0, 0, 0, 1)"> Node reverserLinkByLink(Node node) { </span><span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)"> 指向空, 可以想象成位于第一个节点之前</span> Node newNode = <span style="color: rgba(0, 0, 255, 1)">null</span><span style="color: rgba(0, 0, 0, 1)">; </span><span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)"> 指向第一个节点</span> Node curNode =<span style="color: rgba(0, 0, 0, 1)"> node; </span><span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)"> 循环中, 使用第三变量事先保存curNode的后面一个节点</span> <span style="color: rgba(0, 0, 255, 1)">while</span> (curNode != <span style="color: rgba(0, 0, 255, 1)">null</span><span style="color: rgba(0, 0, 0, 1)">) { Node tempNode </span>=<span style="color: rgba(0, 0, 0, 1)"> curNode.getNext(); </span><span style="color: rgba(0, 128, 0, 1)">//</span><span style="color: rgba(0, 128, 0, 1)"> 把curNode反向往前指</span> 

curNode.setNext(newNode);

讯享网 newNode </span>=<span style="color: rgba(0, 0, 0, 1)"> curNode; curNode </span>=<span style="color: rgba(0, 0, 0, 1)"> tempNode; } </span><span style="color: rgba(0, 0, 255, 1)">return</span><span style="color: rgba(0, 0, 0, 1)"> newNode; } 

}