Offer24（反转链表）

发表于 | 分类于 ，

题目：

　　输入一个链表，反转链表后，输出新链表的表头。

思路：

　　若只定义一个指针进行反转，则会造成链表断开。因此考虑使用多指针暂存后续节点，以防链表断开。同时此题也可以使用递归，利用递归从尾到头反转链表，
代码简洁，但是思路有点绕，需注意。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 递归
   public ListNode ReverseList1(ListNode head) {
   	if (head == null || head.next == null) {
		return head;
	}
   	ListNode node = ReverseList1(head.next);
   	head.next.next = head;
   	head.next = null;
   	return node;
}
   // 双指针
   public ListNode ReverseList2(ListNode head) {
   	if (head == null || head.next == null) {
		return head;
	}
   	ListNode preNode = null;
   	ListNode curNode = head;
   	while(curNode != null) {
   		ListNode temp = curNode.next;
   		curNode.next = preNode;
   		preNode = curNode;
   		curNode = temp;
   	}
   	return preNode;
   }

复杂度分析：

递归

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(n)。

双指针：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(1)。