题目
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
https://leetcode.cn/problems/reverse-linked-list/description/
解法一：迭代
解题思路
head 指向前一个节点 pre，pre 开始时默认为 null，因为链表中最后一个节点的 next 应该是 null。head = [1,2,3,4,5] 为例，结果为 [5,4,3,2,1]。pre = null 。
head.next 指向 pre, 即 节点1 指向 null 。然后将 pre 变为节点1，而 head 变为 节点2。 
head.next 指向 pre, 即节点2 指向 节点1 。然后将 pre 变为节点2，而 head 变为 节点3。
head.next 指向 pre, 即节点3 指向 节点2 。然后将 pre 变为节点3，而 head 变为 节点4。 
head.next 指向 pre, 即节点4 指向 节点3 。然后将 pre 变为节点4，而 head 变为 节点5。 
head.next 指向 pre, 即节点5 指向 节点4 。然后将 pre 变为节点5，而 head 变为 null。 
pre 即为答案。
代码实现
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/class Solution {public ListNode reverseList(ListNode head) {ListNode pre = null;// 循环遍历链表中的每一个节点while(head != null){// 先找出下一个节点ListNode nextNode = head.next;// 将head节点指向前一个进行反转head.next = pre;// 将 pre 指向 headpre = head;// 将 head 指向下一个节点，head = nextNode;}return pre;}}
复杂度分析
n。解法二：递归
解题思路
next）到最后一个节点，然后将反转后的最后一个节点（其实就是第二个节点）指向第一个节点，即 next.next = head，然后 head.next = null （这一步必须有，不然就会形成环路）。next）到最后一个节点，然后将反转后的最后一个节点（其实就是第三个节点）指向第二个节点。next 节点，那么它的反转就是它自己，直接返回。然后按照递归路径逐层返回。head = [1,2,3,4,5] 为例，结果为 [5,4,3,2,1]，如动图所示：
代码实现
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/class Solution {public ListNode reverseList(ListNode head) {if(head == null || head.next == null){return head;}ListNode next = head.next;ListNode reverseNode = reverseList(next);next.next = head;head.next = null;return reverseNode;}}
复杂度分析
n，需要逐层反转每一个节点，时间复杂度为节点个数 n。n，空间复杂度主要取决于递归调用的栈空间，最多为 n 层。本篇文章来源于微信公众号: i余数
微信扫描下方的二维码阅读本文
Comments NOTHING