解法I 自定义顺序栈

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    var st []int
    var top = -1
    p := head
    //遍历链表
    for p!=nil {
        st = append(st,p.Val)
        top++
        p = p.Next
    }


    q := head
    //出栈
    for top >= 0{
        q.Val=st[top]
        q = q.Next
        top--
    }

    return head

}

时间复杂度

遍历2次 O(2n)

空间复杂度

创建了一个顺序栈 O(n)

解法II 迭代

存在链表 1→2→3→∅ ==> ∅←1←2←3

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(first *ListNode) *ListNode {
    p := first

    //前驱结点
    var pre  *ListNode

    for  p != nil {
        temp := p
        p = p.Next
        temp.Next = pre
        pre = temp
    }

    return pre
}

时间复杂度

遍历一次 O(n)

空间复杂度

显然是O(1)

解法III 递归(理解思路即可,递归的本质,只是用了系统自带的栈)

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

时间复杂度

遍历一次 O(n)

空间复杂度

创建了系统栈,显然是O(n)