Reverse a singly linked list.
Hint:A linked list can be reversed either iteratively or recursively. Could you implement both?
反向链表,分别用递归和迭代方式实现。
Java: Iterative solution
public ListNode reverseList(ListNode head) {
ListNode newHead = null;
while (head != null) {
ListNode next = head.next;
head.next = newHead;
newHead = head;
head = next;
}
return newHead;
}Java:Recursive solution
public ListNode reverseList(ListNode head) {
return reverseListInt(head, null);
}
private ListNode reverseListInt(ListNode head, ListNode newHead) {
if (head == null)
return newHead;
ListNode next = head.next;
head.next = newHead;
return reverseListInt(next, head);
} Python: Iteration
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# @param {ListNode} head
# @return {ListNode}
def reverseList(self, head):
dummy = ListNode(0)
while head:
next = head.next
head.next = dummy.next
dummy.next = head
head = next
return dummy.nextPython: Recursion
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# @param {ListNode} head
# @return {ListNode}
def reverseList(self, head):
return self.doReverse(head, None)
def doReverse(self, head, newHead):
if head is None:
return newHead
next = head.next
head.next = newHead
return self.doReverse(next, head)C++: Iteration
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
auto dummy = ListNode{0};
while (head) {
auto tmp = head->next;
head->next = dummy.next;
dummy.next = head;
head = tmp;
}
return dummy.next;
}
};C++: Recursion
class Solution {
public:
/**
* @param head: The first node of linked list.
* @return: The new head of reversed linked list.
*/
ListNode *reverse(ListNode *head) {
if (!head || !head->next) return head;
ListNode *t = head;
head = reverse(t->next);
t->next->next = t;
t->next = NULL;
return head;
}
};类似题目:
[LeetCode] Reverse Linked List II 反向链表II