链表(三)——反转链表

给你单链表的头节点head，请你反转链表，并返回反转后的链表

力扣206 反转链表

示例 ：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

双指针

观察单链表的结构，只需要反转链表指针的指向

• 从头结点的位置开始改变指针指向
• pre指向null,cur指向头结点
• 将cur的指向改为pre
• 用temp储存cur指向的下一个节点，便于下一次反转
• curpre指向都后移一个位置，直至cur指向null
  

class Solution {
    
    public ListNode reverseList(ListNode head) {
    
        ListNode pre = null;
        ListNode cur = head;
        ListNode temp = null;
        while (cur != null) {
    
            temp = cur.next;// 保存下一个节点
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

递归

在双指针中操作是重复的，也可以使用递归

• 确定好边界条件

class Solution {
    
    public ListNode reverseList(ListNode head) {
    
        // 初始化条件
        return reverse(null, head);
    }
    public ListNode reverse(ListNode pre, ListNode cur) {
    
       // 跳出递归的条件
        if (cur == null) {
    
            return pre;
        }
        ListNode temp = null;
        temp = cur.next;// 先保存下一个节点
        cur.next = pre;// 反转
        return reverse(cur, temp); // 更新位置
    }
}