题解 | #反转链表#

（1）定义两个指针： pre 和 cur ；pre 在前 cur 在后。
（2）每次让 pre 的 next 指向 cur ，实现一次局部反转
（3）局部反转完成之后， pre 和 cur 同时往前移动一个位置
（4）循环上述过程，直至 pre 到达链表尾部

图解：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        # 空链表或只有一个节点得链表
        if not pHead&nbs***bsp;not pHead.next:
            return pHead
        cur = pHead
        pre = None
        # 循环移动curent和pre，移动过程中反转 curent.next=pre
        while cur:
            next_node = cur.next
            cur.next = pre
            pre = cur
            cur = next_node
        return pre

复杂度分析：

时间复杂度O(N)：N表示链表长度，双指针一次遍历

空间复杂度O(1)：常数大小空间指针

算法思想二：递归

递归上来就先写终止条件：如果head为空或者head.next为空，返回head
（1）新头结点 res 指向尾结点，此处进入递归，递归一直到遍历到尾结点时才会返回
（2）每一层递归，该层递归中的 head 会让下一个节点指向自己，head.next.next = head；然后head自己指向空。以此达到反转的目的。
（3）返回新链表的头结点newHead

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode res = ReverseList(head.next);
        head.next.next = head;
        head.next = null;
        return res;
    }
}

复杂度分析：

解题思路：

新建额外的新栈 stack

循环遍历原链表，并将链表元素入栈，遍历结束后，将栈内元素依次出栈并建立链表

图解：

public ListNode ReverseList(ListNode head) {
    Stack<ListNode> stack = new Stack<>();
    //把链表节点全部摘掉放到栈中
    while (head != null) {
        stack.push(head);
        head = head.next;
    }
    if (stack.isEmpty())
        return null;
    ListNode node = stack.pop();
    ListNode dummy = node;
    //栈中的结点全部出栈，然后重新连成一个新的链表
    while (!stack.isEmpty()) {
        ListNode tempNode = stack.pop();
        node.next = tempNode;
        node = node.next;
    }
    //最后一个结点就是反转前的头结点，一定要让他的next
    //等于空，否则会构成环
    node.next = null;
    return dummy;
}