206 - Reverse Linked List

Reverse Linked List

Reverse a singly linked list.

click to show more hints.

Hide Tags

Linked List

Hide Similar Problems

(M) Reverse Linked List II (M) Binary Tree Upside Down (E) Palindrome Linked List

 

前些时候做的，写了递归和迭代两个版本。

递归的版本比较好玩，曾经见过一个讨论说到有用栈的，另外就有人说可以用递归，

一路到底，然后在每次返回的时候把next反向指回来，也就实现了反转，当然，会有O(n)的空间开销。

 

/**
* 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) {
        ListNode dummy(0);
        dummy.next = head;
        rev_recursive(&dummy, head, &(dummy));
        //rev_iteratively(&dummy);
        return dummy.next;
    }
   
    void rev_recursive(ListNode* pre, ListNode* node, ListNode* dummy)
    {
        if(NULL == node)
            return;
       
        if(NULL == node->next)
            dummy->next = node;

        rev_recursive(node, node->next, dummy);
       
        if(pre!=dummy)
            node->next = pre;
        else
            node->next = NULL;
           
        return;
    }
   
    void rev_iteratively(ListNode* head)
    {
        ListNode* node = head->next;
        ListNode* prev = head;
        ListNode* next = head->next;
        while(node)
        {
            if(NULL == node->next)
                head->next = node;
           
            next = node->next;

            if(head == prev)
                node->next = NULL;
            else
                node->next = prev;

            prev = node;
            node = next;
        }
        return;
    }
};

8 ms.