-
Notifications
You must be signed in to change notification settings - Fork 8
/
ReverseLinkedList.java
74 lines (64 loc) · 2.08 KB
/
ReverseLinkedList.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
package linkedlist;
// Source : https://leetcode.com/problems/reverse-linked-list/
// Id : 206
// Author : Fanlu Hai | https://github.com/Fanlu91/FanluLeetcode
// Date : 2019-05-29
// Topic : Double Pointers, Recursive
// Level : Easy
// Other :
// Tips : Must
// Links :
// Result : 100.00% 99.87%
public class ReverseLinkedList {
// 100.00% 99.87%
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode pre = null, cur = head, next;
while (cur != null) {
next = cur.next; // 1. save next pointer
cur.next = pre; // 2. reverse current node
// 3. advance current and prev
pre = cur;
cur = next;
}
// from the last iteration, pre pointed to current node which does not have a next,
// it means pre is the new head
return pre;
}
// 100.00% 99.87%
public ListNode reverseListRecursive(ListNode cur) {
if (cur == null || cur.next == null)
return cur;
/**
* 1. before current node reverse, make sure from current's next all nodes has been reversed already.
* 2. if so, reverse current by point current's next node's next pointer to current
* and make current point to none
* 3. if current is somebody else's next, its pointer will be assigned during that process
* otherwise current is the new tail.
*/
ListNode newHead = reverseListRecursive(cur.next);
//reverse current cur
cur.next.next = cur;
cur.next = null;
return newHead;
}
public ListNode reverseList1(ListNode head) {
// public ListNode reverseList(ListNode head) {
ListNode newHead = null, p = head;
while (p != null) {
ListNode tmp = p.next;
p.next = newHead;
newHead = p;
p = tmp;
}
return newHead;
}
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
}