题解 | #反转链表#
反转链表
http://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca
算法思想一：双指针迭代
解题思路：
（1）定义两个指针： pre 和 cur ；pre 在前 cur 在后。
（2）每次让 pre 的 next 指向 cur ，实现一次局部反转
（3）局部反转完成之后， pre 和 cur 同时往前移动一个位置
（4）循环上述过程，直至 pre 到达链表尾部
（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
（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;
}
} 复杂度分析：
时间复杂度O(N)：N表示链表长度
空间复杂度O(N)：递归机制的实现需要借助于栈，该程序中递归栈的深度为N-1，所以空间复杂度为线性。
算法思路三：使用额外栈
解题思路：
新建额外的新栈 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;
} 复杂度分析：
时间复杂度O(N)：N表示链表长度
空间复杂度O(N)：辅助栈空间
