-
Notifications
You must be signed in to change notification settings - Fork 147
/
ReverseList16.java
69 lines (62 loc) · 1.54 KB
/
ReverseList16.java
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
package com.so;
import com.so.Common.ListNode;
/**
* 第16题 反转链表
* 输入一个链表的头结点,反转该链表并输出翻转后的头结点
*
* @author qgl
* @date 2017/08/10
*/
public class ReverseList16 {
/**
* 解法一:迭代:两个指针,反向输出
* 时间复杂度:O(n),空间复杂度:O(1)
*
* @param head
* @return
*/
public static ListNode reverseList1(ListNode head) {
ListNode pre = null;
ListNode curr = head;
while (curr != null) {
ListNode tmp = curr.next;
curr.next = pre;
pre = curr;
curr = tmp;
}
return pre;
}
/**
* 解法二:迭代:单指针依次往后移动,改变原节点间的指向
* 时间复杂度:O(n),空间复杂度:O(1)
*
* @param head
* @return
*/
public static ListNode reverseList2(ListNode head) {
ListNode pre = null;
while (head != null) {
ListNode p = head.next;
head.next = pre;
pre = head;
head = p;
}
return pre;
}
/**
* 解法三:递归
* 时间复杂度:O(n),空间复杂度:O(n)
*
* @param head
* @return
*/
public static ListNode reverseList3(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode p = reverseList3(head.next);
head.next.next = head.next;
head.next = null;
return p;
}
}