目录
难度:简单
今天刷反转链表,大家有兴趣可以点上看看题目要求,试着做一下。
方法1、迭代(时间复杂度(1))
方法2、递归(时间复杂度(n))
这道题是不难,应该算是基础的题目了,递归方法比较难理解一点
假设链表为1->2->3->null,我们需要把它改成null->1->2->3
在遍历链表时,将当前节点的next 指针改为指向前一个节点,由于节点没有设引用前一个节点,因此必须事先存储其前一个节点,在更改的引用之前,由于节点没有设引用前一个节点,最后返回新的头引用。
- class Solution {
- public ListNode reverseList(ListNode head) {
- ListNode cur = head, pre = null;//头节点
- while(cur != null) {
- ListNode tmp = cur.next; // 暂存后继节点 cur.next
- cur.next = pre; // 修改 next 引用指向
- pre = cur; // pre 暂存 cur
- cur = tmp; // cur 访问下一节点
- }
- return pre;
- }
- }
-
-
-
- class Solution {
- public ListNode reverseList(ListNode head) {
- return recur(head, null); // 调用递归并返回
- }
- private ListNode recur(ListNode cur, ListNode pre) {
- if (cur == null) return pre; // 终止条件
- ListNode res = recur(cur.next, cur); // 递归后继节点
- cur.next = pre; // 修改节点引用指向
- return res; // 返回反转链表的头节点
- }
- }
-