206.反转链表.md

206. 反转链表

题目描述

给你单链表的头节点 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

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/reverse-linked-list

解题步骤

这个题解法有两种，一种迭代法，一种递归法, 但核心思路都是一样的

以递归法为例： 如1->2->3->null链表需要翻转 结果就是3->2->1->null

当遍历到2(head)->3(head.next)->null时 我们要做的是3->2->null分解下步骤

step1: 让3->2 即head.next.next = head

Step2: 让2->null 即head.next = head.next.next

需要注意的是head.next.next地址需要提前保存 否则在step1修改后 在step2里就是更新后的结点地址了

代码如下

递归法

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    newHead := reverseList(head.Next)

    //把当前节点下一个的下一个节点存起来
    tmp := head.Next.Next
    // 下一个节点的下一个指向反转  即1(head)->2(head.next)->null 改为1(head)->2(head.next) 1(head)<- 2(head.next)  null(tmp)
    head.Next.Next = head
    //将当前节点下一个指向连接到下一个的下一个的节点即   null<-1(head)<-2(head.next)
    head.Next = tmp

    return newHead
}

// 优化版
func reverseList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	node := reverseList(head.Next)
	head.Next.Next = head
	head.Next = nil // 当前head是最后一位 所以可以直接用nil赋值

	return node
}

时间复杂度 O(n) 数组长度

空间复杂度 O(n) 递归深度即链表长度

迭代法

迭代法和递归法相比较， 只关心当前节点指向的翻转 cur.next = prev即可 返回最后一个节点

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    var prev *ListNode  //前面结点记录下来
    cur := head 
    for cur != nil {
        tmp := cur.Next  //暂存下一个节点地址
        cur.Next = prev //当前节点的下一个指向翻转

        prev = cur //更新上一个节点
        cur = tmp  
    }
    return prev
}

时间复杂度 O(n) 数组长度

空间复杂度 O(1)