第 24 题：输入一个链表，反转链表后，输出链表的所有元素
传送门：AcWing：反转链表，牛客网 online judge 地址。
定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。
样例：
输入：
1->2->3->4->5->NULL输出：
5->4->3->2->1->NULL
分析：这道题同 LeetCode 上一道问题，可以使用“穿针引线”也可以使用递归求解。个人觉得递归的方式比较简单，但是在链表较长的时候，递归效率偏低，因为要使用系统栈。
思路1：递归。
Python 代码：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
# 递归写法：用递归就不用思考穿针引线这种事情了。
class Solution:
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
# 递归的终止条件一定要写对：考虑结点为空和单结点的情况
if head is None or head.next is None:
return head
next = head.next
new_head = self.reverseList(next)
next.next = head
head.next = None
return new_head
Java 代码：
class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
public class Solution {
// 递归写法要画个图就清楚了
public ListNode ReverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode next = head.next;
ListNode newHead = ReverseList(next);
next.next = head;
head.next = null;
return newHead;
}
}
思路2：非递归写法，穿针引线。
《剑指 Offer》（第 2 版）第 24 题：反转链表
Python 代码：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
# 穿针引线，可以看到 while 循环体部分的代码是首尾相连的，有些单链表的题目也有这种规律，感觉很神奇
# 在 Python 中，其实还有更简便的写法，就跟斐波拉契数列一样
class Solution:
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
pre = None
cur = head
while cur:
next = cur.next
cur.next = pre
pre = cur
cur = next
return pre
