leetcode 206.反转链表(链表)

阅读数: 次 2020-04-27

题目描述

反转一个单链表。

示例：

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

解法

1.迭代

图解：

fanzhuandiedai

代码实现：

public ListNode reverseList(ListNode head) {
    //定义两个结点：前结点，当前结点
    ListNode pre = null;
    ListNode cur = head;
    /*思路
		 *	1 -> 2 -> 3 -> 4 -> 5 -> null
		 *	null <- 1 <- 2 <- 3 <- 4 <- 5
		 */
    while(cur!=null) {
        ListNode temp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = temp;
    }
    return pre;
}

时间复杂度：O(n)，假设 n 是列表的长度，时间复杂度是 O(n)。
空间复杂度：O(1)。

2.递归

图解：

fanzhuandigui

代码实现：

public ListNode reverseList(ListNode head) {
    if(head==null||head.next==null)return head;
    ListNode cur = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return cur;
}

此递归较难理解，在此引用leetcode用户懒懒米虫的思路

不妨假设链表为1，2，3，4，5。按照递归，当执行reverseList（5）的时候返回了5这个节点，reverseList(4)中的p就是5这个节点，我们看看reverseList（4）接下来执行完之后，5->next = 4, 4->next = null。这时候返回了p这个节点，也就是链表5->4->null，接下来执行reverseList（3），代码解析为4->next = 3,3->next = null，这个时候p就变成了，5->4->3->null, reverseList(2), reverseList(1)依次类推，p就是:5->4->3->2->1->null

可能这个看完了你还是不明白为什么返回cur，这里给出自己的理解

第一个if判断第一次触发终止条件时head=5，然后下一层 ListNode cur = reverseList(head.next);

cur拿到的就是5即cur=5，即首地址就为5的那个，然后后面递归完成我们可以通过首地址访问到一整个链表

时间复杂度：O(n)，假设 n 是列表的长度，那么时间复杂度为 O(n)。
空间复杂度：O(n)，由于使用递归，将会使用隐式栈空间。递归深度可能会达到 n 层。

作者：LeetCode
链接：https://leetcode-cn.com/problems/reverse-linked-list/solution/fan-zhuan-lian-biao-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

结语

今天JD3:0FPX属实上流哦🍷

昔日御三家，如今六七八。昔日世界冠，如今季军战

今天歌纯属看名字，质量应该不咋地