题目：定义一个函数，输入一个链表的头结点，反转该链表并输出反转后的链表的头结点。

解题思路：单向链表只能实现单向遍历，改变链表方向就是要把当前链表的节点指向它的前一个节点，

一旦当前链表指向发生了变化，就不能根据此节点获取到它后面的节点，所以在改变方向前要保存当前节点的下一节点，防止链表断开，

因此需要三个指针来保存当前节点，当前节点的前节点，当前节点的下节点。

注意：如果当前节点没有下一节点，则此节点就是反转后的链表的头结点。

另外一种解决办法是使用一个栈结构，顺序遍历链表，把每个节点依次入栈。待全部节点入栈后，依次把节点从栈中取出并连接，这样得到的链表也是反转后的链表。

1 package Solution; 2  3  4 public class No16ReverseList { 5  6     public static class ListNode { 7         int data; 8         ListNode next; 9 10         public ListNode() {11 12         }13 14         public ListNode(int value, ListNode next) {15             this.data = value;16             this.next = next;17         }18     }19 20     public static ListNode reverseList(ListNode head) {21         if (head == null)22             throw new RuntimeException("invalid List,can't be null");23         if (head.next == null)24             return head;25         ListNode reversedHead = null;26         ListNode node = head;27         ListNode preNode = null;28         while (node != null) {29             ListNode nextNode = node.next;30             if (nextNode == null)31                 reversedHead = node;32             // 赋值顺序不能变33             node.next = preNode;34             preNode = node;35             node = nextNode;36         }37         return reversedHead;38     }39 40     public static void print(ListNode head) {41         if (head == null)42             System.out.println("当前链表为空");43         while (head != null) {44             System.out.print(head.data + ",");45             head = head.next;46         }47     }48 49     public static void main(String[] args) {50         ListNode node1 = new ListNode(4, null);51         ListNode node2 = new ListNode(3, node1);52         ListNode node3 = new ListNode(2, node2);53         ListNode node4 = new ListNode(1, node3);54 55         print(reverseList(node4));56         System.out.println();57         print(reverseList(new ListNode(5, null)));58         System.out.println();59         print(reverseList(new ListNode()));60         System.out.println();61     }62 63 }