206. 反转链表(2)

题目地址(206. 反转链表)

https://leetcode-cn.com/problems/reverse-linked-list/

题目描述

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
提示：
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

前置知识

公司

• 暂无

思路

只需要改变链表的next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表

关键点

代码

• 语言支持：Java

Java Code:

• 双指针法

  class Solution {
        public ListNode reverseList(ListNode head) {
            //前指针指向一个虚拟的节点 值为空
            ListNode pre = null;
            ListNode cur = head;
            //定义一个临时节点 存放cur.next 不然这个值在更改了cur的指向后就会丢失
            ListNode tempNode = head;
            while (cur != null) {
                //先保存下一个节点
                tempNode = cur.next;
                //反转
                cur.next = pre;
                //更新prev、cur位置    
                pre = cur;
                cur = tempNode;
            }
            return 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){
            return reverse(null, head);
        }
        public ListNode reverse(ListNode pre,ListNode cur) {
            if (cur == null) {
                return pre;
            }
            ListNode tempNode = null;
            tempNode = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tempNode;
            return reverse(pre, cur);
        }
    }

复杂度分析

令 n 为数组长度。

• 时间复杂度：#card=math&code=O%28n%29&id=Y9AVE)
• 空间复杂度：#card=math&code=O%28n%29&id=B4IG9)