206. Reverse Linked List
Difficulty: Easy
Reverse a singly linked list.
Example:
1
2
|
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
|
Follow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?
Solution
Language: Ruby
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
def (head)
end
|
解法
解法一
非递归解法
1
2
3
4
5
6
7
8
9
10
11
|
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
|
解法二
非递归解法
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
dummy = ListNode(0)
while head:
dummy.next, head.next, head = head, dummy.next, head.next
return dummy.next
|
解法三
递归解法，重要！重要！重要！
1
2
3
4
5
6
7
|
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode p = reverseList(head.next);
head.next.next = head;
head.next = null;
return p;
}
|
近期评论