-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path0206_reverse_linked_list.java
More file actions
55 lines (45 loc) · 1.15 KB
/
0206_reverse_linked_list.java
File metadata and controls
55 lines (45 loc) · 1.15 KB
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
/*
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
*/
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
// 迭代版本
class MySolution {
public ListNode reverseList(ListNode head) {
ListNode last = null, next = null;
while (head != null) {
next = head.next; // 原序的下一节点
head.next = last;
last = head;
head = next;
}
return last;
}
}
// 递归版本
class MySolution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
head = reverse(head, null);
return head;
}
private ListNode reverse(ListNode head, ListNode last) {
if (head == null) return last;
ListNode next = head.next;
head.next = last;
last = head;
head = next;
return reverse(head, last);
}
}