知一的指纹

206. 反转链表

版权声明: 本文为博主原创文章,发表自 知一的指纹。转载需向 我的邮箱 申请。

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
public class ReverseLinkedList {
public static void main(String[] args) {
ListNode listNode = ListNode.of(
1,
ListNode.of(
2,
ListNode.of(
3,
ListNode.of(
4,
ListNode.of(
5, null
)
)
)
)
);
ListNode next = listNode;
while (null != next) {
System.out.println(next.val);
next = next.next;
}

System.out.println("===");
ListNode reverse = reverse3(listNode);

ListNode next2 = reverse;
while (null != next2) {
System.out.println(next2.val);
next2 = next2.next;
}
}

/**
* 官方推荐的
* @param head
* @return
*/
public static ListNode reverse2(ListNode head) {
// prev -> curr -> nextTemp
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}

/**
* 自己写的
* @param head
* @return
*/
public static ListNode reverse(ListNode head) {
// cur -> prev -> tmp
ListNode cur = head;
ListNode next = head.next;
head.next = null;
while (null != cur) {
ListNode tmp = null;
if (null != next) {
tmp = next.next;
next.next = cur;
}
if (null == next) {
break;
}
cur = next;
next = tmp;
}
return cur;
}

/**
* 复写的
* 1. 记录前一个节点,当前节点
* 2. 迭代
* 3. 取出当前节点到临时变量
* 4. -- 现在有 prev -> curr -> next 三个节点
* 5. 将 curr.next -> prev,改变指向方向
* 6. 依次挪动节点位置 prev = curr , curr = nextTemp
* 7. 最后返回 prev
*
* 时间复杂度 O(n)
* 空间复杂度 O(1)
* @param head
* @return
*/
public static ListNode reverse3(ListNode head) {
// prev -> curr -> next
ListNode prev = null;
ListNode curr = head;
while (null != curr) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}

如果此文章能给您带来小小的提升,不妨小额赞赏我一下,以鼓励我写出更好的文章!
Noogel's WeChat Pay

微信打赏

Noogel's Alipay

支付宝打赏