单链表反转

题目:反转一个单链表

/**
 * 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 *reverseHead = NULL;
        ListNode *node = head;
        ListNode *pre= NULL;
        while(node != NULL)
        {
            ListNode *next = node->next;
            if(next == NULL)
                reverseHead = node;
            node->next = pre;
            pre = node;
            node = next;
        }
        return reverseHead;
/** another version
        if(!pHead)
            return pHead;
        
        ListNode* curr = pHead;
        ListNode* prev = NULL;
        ListNode* next;
        while(curr->next){
            next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        
        curr->next = prev;
        return curr;
*/
    }
};

逆序输出单链表

void PrintReverseLink(ListNode *head)
{
    if(head->next != NULL){
       PrintReverseLink(head->next);
       printf("%d ",head->next->val);
    }
}

 

ListNode *reverse(ListNode *p, ListNode* &head)
{
   if(p == NULL || p->next == NULL)
   {
      head = p;
      return p;
    }
    else
    {
      ListNode *data = reverse(p->next, head);
      data->next = p;
      return data;
    }
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *