题目描述
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
解题思路
链表一般都是用迭代或是递归法来解决，而且一般都是构造双指针、三指针，比如反转链表或是DP动态规划。
双指针迭代
我们可以申请两个指针，第一个指针叫 pre，最初是指向 null 的。
第二个指针 cur 指向 head，然后不断遍历 cur。
每次迭代到 cur，都将 cur 的 next 指向 pre，然后 pre 和 cur 前进一位。
都迭代完了(cur 变成 null 了)，pre 就是最后一个节点了。
java实现
class Solution { public ListNode reverseList(ListNode head) { //申请结点，pre和 cur，pre指向null ListNode pre = null; ListNode cur = head; ListNode tmp = null; while(cur!=null) { //记录当前节点的下一个节点 tmp = cur.next; //然后将当前节点指向pre cur.next = pre; //pre和cur节点都前进一位 pre = cur; cur = tmp; } return pre; } }
Python实现
class Solution(object): def reverseList(self, head): if not head or not head.next: return head l = head r = head.next remain = r.next l.next = None while r: r.next = l l = r r = remain if remain: remain = remain.next return l
递归实现：
递归的两个条件：
- 终止条件是当前节点或者下一个节点==null
- 在函数内部，改变节点的指向，也就是 head 的下一个节点指向 head 递归函数那句
head.next.next = head很不好理解，其实就是 head 的下一个节点指向head。
递归函数中每次返回的 cur 其实只最后一个节点，在递归函数内部，改变的是当前节点的指向。
class Solution { public ListNode reverseList(ListNode head) { //递归终止条件是当前为空，或者下一个节点为空 if(head==null || head.next==null) { return head; } //这里的cur就是最后一个节点 ListNode cur = reverseList(head.next); //如果链表是 1->2->3->4->5，那么此时的cur就是5 //而head是4，head的下一个是5，下下一个是空 //所以head.next.next 就是5->4 head.next.next = head; //防止链表循环，需要将head.next设置为空 head.next = null; //每层递归函数都返回cur，也就是最后一个节点 return cur; } }
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def reverseList(self, head: ListNode) -> ListNode: if not head or head.next == None: return head res = self.reverseList(head.next) head.next.next = head head.next = None return res
