反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
解法一：
迭代求解。
public ListNode reverseList(ListNode head) {
//如果 head 为空或者 head.next 的下一点结点为空，则返回 head
if (head == null || head.next == null) {
return head;
}
ListNode cur = null;
ListNode pre = null;
while (head != null) {
//cur 为 head 的下一个结点
cur = head.next;
//这里发生反转，head 的下一个结点指向 pre，即 head 的上一个结点
head.next = pre;
//pre 变成 head，即 pre 的下一个结点
pre = head;
//head 变成 head 的下一个结点
head = cur;
}
return pre;
}
解法二：
递归求解。
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
//此时返回链表的最后一个结点
return head;
}
ListNode listNode = reverseList(head.next);
//这里发生了反转
head.next.next = head;
//置为 null 不影响链表的值，因为 head.next 的值已经作为参数传递了
head.next = null;
//这里返回的也是最后一个结点
return listNode;
}
