力扣 206. 反转链表

206. 反转链表

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

思路一：三个指针迭代

三个指针往后移，当 cur 指针为空时跳出循环

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) { val = x; }
 7  * }
 8  */
 9 class Solution {
10     public ListNode reverseList(ListNode head) {
11         ListNode pre = null;
12         ListNode cur = head;
13         ListNode nextNode = null;
14         while(cur != null){
15             nextNode = cur.next;
16             cur.next = pre;
17             pre = cur;
18             cur = nextNode;
19         }
20         return pre;
21     }
22 }

力扣测试时间为：0ms，空间为39.8MB

复杂度分析：

时间复杂度：因为只扫描了一遍链表，所以时间复杂度为O(n)

空间复杂度为O(1)

思路二：递归方式

递归，先递归到最后一个结点，返回到上一层后让head.next.next指向head,让一个往后指的指针往回指,每次都返回链表的最后的那个节点

 1 class Solution {
 2     // 递归，先递归到最后一个结点，返回到上一层后让head.next.next指向head,
 3     // 让一个往后指的指针往回指,每次都返回链表的最后的那个节点
 4     public ListNode reverseList(ListNode head) {
 5         if(head == null || head.next == null)
 6             return head;
 7         ListNode p = reverseList(head.next);
 8         head.next.next = head;
 9         head.next = null;
10         return p;
11     }
12 }

力扣测试时间为：0ms，空间为39.8MB

复杂度分析：

时间复杂度：需要遍历两次链表，一次是不断递归直到最后一个结点，另一次是从最后一个结点往前反转，所以时间复杂度为O(n)

空间复杂度：递归的深度为O(n),所以空间复杂度为O(n)

思路转自：

https://leetcode-cn.com/problems/reverse-linked-list/solution/fan-zhuan-lian-biao-by-leetcode/