Reverse a singly linked list.

Hint:

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;

    }

};

类似题目：

[LeetCode] Reverse Linked List II 反向链表II

All LeetCode Questions List 题目汇总

巴特西

[LeetCode] 206. Reverse Linked List 反向链表

All LeetCode Questions List 题目汇总

最新文章

热门文章