Online Judge Solutions

Friday, January 2, 2015

Reverse Linked List

Reverse a linked list.
Example
For linked list 1->2->3, the reversed linked list is 3->2->1
Challenge
Reverse it in-place and in one-pass
ListNode *reverse(ListNode *head) {
        if (!head) return head;
        
        ListNode dummy(0);
        dummy.next = head;
        
        ListNode *p = &dummy;
        while(head->next) {
            ListNode *T = head->next;
            head->next = T->next;
            T->next = p->next;
            p->next = T; 
        }
        
        return dummy.next;
    }
 ListNode *reverse(ListNode *head) {
        ListNode *prev = NULL;
        while(head) {
            ListNode* T = head->next;
            head->next = prev;
            prev = head;
            head = T;
        }
        
        return prev;
    }

No comments:

Post a Comment