-
Notifications
You must be signed in to change notification settings - Fork 187
/
206. Reverse Linked List.java
80 lines (70 loc) · 2 KB
/
206. Reverse Linked List.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
206. Reverse Linked List
// https://leetcode.com/problems/reverse-linked-list/
Solution 1: iterative
public ListNode reverseList(ListNode head) {
ListNode newHead = null;
while(head != null) {
ListNode next = head.next;
head.next = newHead;
newHead = head;
head = next;
}
return newHead;
}
Solution 2: recursive
public ListNode reverseList(ListNode head) {
return helper(head, null);
}
private ListNode helper(ListNode cur, ListNode newHead) {
if (cur == null) return newHead;
ListNode next = cur.next;
cur.next = newHead;
return helper(next, cur);
}
变种:
print linkedlist reversely, recursive (print linked list, no reverse)
if cannot use recursion, cannot modify the linkedlist, we can use StringBuilder.reverse().toString()
1,递归:
public void reverseList(ListNode head) {
if (head == null) return;
reverseList(head.next);
System.out.print(head.val + " ");
}
2,非递归:
public void print(ListNode head){
Stack<ListNode> stack = new Stack<>();
while (head != null) {
stack.push(head);
head = head.next;
}
while (!stack.isEmpty())
System.out.println(stack.poll().val);
}
Follow Up:
if we need to use O(logn) space ? we can use recursion to print the right part, and then the left part
Solution: D & C
O(nlogn) time, O(logn) space
public void reverseList(ListNode head) {
if (head == null) return;
ListNode curr = head;
int length = 0;
while (curr != null) {//get the total length
curr = curr.next;
length++;
}
helper(head, length);
}
private void helper(ListNode head, int length) {
if (length == 1) {
System.out.print(head.val + " ");
return;//remember to return !!!
}
ListNode curr = head;
int count = 0;
while (count < length / 2) {
curr = curr.next;
count++;
}
helper(curr, length - length / 2);//note that the right part has length - length / 2 nodes
helper(head, length / 2);
}