Reverse a singly linked list.
A linked list can be reversed either iteratively or recursively. Could you implement both?
反向链表，分别用递归和迭代方式实现。
递归Iteration：
新建一个node(value=任意值, next = None)， 用一个变量 next 记录head.next，head.next指向新node.next，新 node.next 指向head，next 进入下一个循环，重复操作，直到结束。
迭代Recursion：
假设有链表1 -> 2 -> 3 -> 4 -> 5要进行反转，第一层先把1 -> 2 -> 3 -> 4 -> 5和None传入递归函数(head, newhead)，先记录head的next(2 -> 3 -> 4 -> 5)，head(1)指向newhead(None)变成(1->None)，然后把(2 -> 3 -> 4 -> 5, 1 -> None)递归传入下一层，记录head的next(3 -> 4 -> 5)，head(2)指向newhead(1->None)变成(2 -> 1->None)，然后把(3 -> 4 -> 5, 2 -> 1 -> None)递归传入下一层，直到最后head=None时返回newhead，此时 newhead = 5 -> 4 -> 3 -> 2 -> 1 -> None
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
def reverseList(self, head):
prev = None
while head:
curr = head
head = head.next
curr.next = prev
prev = curr
return prev
Python: Iteration
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
cur, prev = head, None
while cur:
cur.next, prev, cur = prev, cur, cur.next
return prev
Python: Iteration
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None def __repr__(self):
if self:
return "{} -> {}".format(self.val, repr(self.next)) class Solution:
def reverseList(self, head):
dummy = ListNode(0)
while head:
next = head.next
head.next = dummy.next
dummy.next = head
head = next
return dummy.next
Python: Recrusion
class Solution(object):
def reverseList(self, head, prev=None):
if not head:
return prev curr, head.next = head.next, prev
return self.reverseList(curr, head)
Python: Recursion
class Solution:
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)
Python: Recursion, wo
class Solution(object):
def reverseList(self, head):
dummy = ListNode(0)
cur = self.recur(head, dummy)
return cur.next def recur(self, head1, head2):
if not head1:
return head2 next_node = head1.next
head1.next = head2.next
head2.next = head1
return self.recur(next_node, head2)
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;
}
};
类似题目：