题目：定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。
解法1：记录3个结点：当前处理结点、前驱结点、后继结点
代码如下：
package demo;
public class Test16 {
public static class ListNode {
int value;
ListNode next;
}
/**
* 记录3个结点：当前处理结点、前驱结点、后继结点
* @param head
* @return
*/
public static ListNode reverseList(ListNode head) {
ListNode reverseHead = null; // 反转后的链表头结点
ListNode curr = head; // 当前处理的结点
ListNode pre = null; // 当前处理的结点的前驱结点
ListNode next = null; // 当前处理的结点的后继结点
while(curr != null) {
// curr后面的指针会断开，因此先记录后继结点
next = curr.next;
// 如果后继结点为空，说明该结点为尾结点，也就是反转后的结点的头结点
if(next == null) {
reverseHead = curr;
}
// 把curr的下一个结点指向它的前驱结点
curr.next = pre;
// 把当前结点作为前驱结点
pre = curr;
// 将之前的后继结点作为当前处理的结点，继续向下处理
curr = next;
}
return reverseHead;
}
public static void printList(ListNode head) {
while(head != null) {
System.out.print(head.value + "->");
head = head.next;
}
System.out.println("null");
}
public static void main(String[] args) {
ListNode head = new ListNode();
head.value = 1;
head.next = new ListNode();
head.next.value = 2;
head.next.next = new ListNode();
head.next.next.value = 3;
head.next.next.next = new ListNode();
head.next.next.next.value = 4;
head.next.next.next.next = new ListNode();
head.next.next.next.next.value = 5;
head.next.next.next.next.next = new ListNode();
head.next.next.next.next.next.value = 6;
System.out.println("打印原单链表：");
printList(head);
System.out.println("反转后的单链表的头结点：");
ListNode reverseHead = reverseList(head);
System.out.println(reverseHead.value);
System.out.println("打印反转后的单链表：");
printList(reverseHead);
}
}
运行结果
解法2：借助临时结点
代码如下：
package demo;
public class Test16 {
public static class ListNode {
int value;
ListNode next;
}
/**
* 借助临时结点
* @param head
* @return
*/
public static ListNode reverseList(ListNode head) {
// 创建一个临时结点
ListNode tmp = new ListNode();
// 临时结点的后继结点为空
tmp.next = null;
// 反转后的链表头结点
ListNode reverseHead = null;
// 当前处理结点
ListNode curr = head;
// 当前处理结点的下一个结点
ListNode next = null;
while(curr != null) {
// curr后面的指针会断开，因此先记录后继结点
next = curr.next;
if(next == null) {
reverseHead = curr;
}
// 将当前结点的后继结点指向临时结点的后继结点
curr.next = tmp.next;
// 将当前结点作为临时结点的后继结点
tmp.next = curr;
// 将下一个待处理结点作为当前结点，继续向下处理
curr = next;
}
return reverseHead;
}
public static void printList(ListNode head) {
while(head != null) {
System.out.print(head.value + "->");
head = head.next;
}
System.out.println("null");
}
public static void main(String[] args) {
ListNode head = new ListNode();
head.value = 1;
head.next = new ListNode();
head.next.value = 2;
head.next.next = new ListNode();
head.next.next.value = 3;
head.next.next.next = new ListNode();
head.next.next.next.value = 4;
head.next.next.next.next = new ListNode();
head.next.next.next.next.value = 5;
head.next.next.next.next.next = new ListNode();
head.next.next.next.next.next.value = 6;
System.out.println("打印原单链表：");
printList(head);
System.out.println("反转后的单链表的头结点：");
ListNode reverseHead = reverseList(head);
System.out.println(reverseHead.value);
System.out.println("打印反转后的单链表：");
printList(reverseHead);
}
}
