/
ReverseList.java
84 lines (77 loc) · 2.18 KB
/
ReverseList.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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
package highFrequencyLeetcode.leetcode_206;
import leetcode.linkedlist.ListNode;
/**
* <p>
*
* 反转一个单链表。
*
* 示例:
*
* 输入: 1->2->3->4->5->NULL
* 输出: 5->4->3->2->1->NULL
*
* 进阶:
* 你可以迭代或递归地反转链表。你能否用两种方法解决这道题?
*
* 定义一个函数,输入一个链表的第一个结点,反转该链表并输出反转后链表的第一个结点。
*
* </p>
*
* @author Seina
* @version 2019-01-03 23:26:18
*
*
*/
public class ReverseList {
/**
* 解法1 迭代法
* @param head :头结点
*
* 时间复杂度 O(n)
* 空间复杂度 O(1)
*
*/
public ListNode reverseList1(ListNode head){
if (head == null || head.next == null) {
return head;
}
ListNode pre= null;
ListNode cur = head;
ListNode next;
while (cur != null){
//将当前结点指向的下一个结点存起来赋值给next结点
next = cur.next;
//开始改变当前结点的指针 --> 指向上一个结点
cur.next = pre;
//开始移动指针,pre --> 移动到 cur
pre = cur;
//cur移动到最先存好的next
cur = next;
}
return pre;
}
/**
* 解法1 递归
*
* @param head :头结点
*
* 时间复杂度 O(n)
* 空间复杂度 O(n)
*
*/
public ListNode reverseList2(ListNode head){
//递归终止条件(newHead 指向尾节点)
if (head == null || head.next == null) {
return head;
}
ListNode newHead = reverseList2(head.next);
//当前节点的下一个节点的下一个节点指向自己
//简单理解就是由 1 -> 2 变成 1 <- 2
head.next.next = head;
//当前节点指向 null(递归结束的时候,这里就是尾节点指向 null)
head.next = null;
//newHead 经过层层递归,从正序链表的头节点走到尾节点(也就是反转的链表的首节点)
//归来过程 newHead 一直都指向尾节点,归来的过程没有移动
return newHead;
}
}