About usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar

Reverse Linked List Problem

Given a linked list, zip it from its two ends in place, using constant extra space. The nodes in the resulting “zipped” linked list should go in this order: first, last, second, second last, and so on.

Follow up:

Implement functions to zip two linked lists and to unzip such that unzip(zip(L1, L2)) returns L1 and L2.

Example One

Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL

Output: 1 -> 6 -> 2 -> 5 -> 3 -> 4 -> NULL

Example Two

Input: 1 -> 2 -> 3 -> 4 -> 5 -> NULL

Output: 1 -> 5 -> 2 -> 4 -> 3 -> NULL

Notes:

Constraints:

● 0

● -2 * 10^9

Solution

We've provided one solution:

1. Split the given list into halves so that, for example, 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL becomes 1 -> 2 -> 3 -> NULL and 4 -> 5 -> 6 -> NULL.

2. Reverse the second list. In this example the second list becomes 6 -> 5 -> 4 -> NULL.

3. Now merge the two lists by alternating the nodes from first and second lists. Build the resulting list by updating the “next” pointers of the nodes.

Time Complexity:

O(n).

Auxiliary Space Used:

O(1).

Space Complexity:

O(n).


// Reverse singly linked list in O(len) time and O(1) space. 
LinkedListNode *reverse_linked_list(LinkedListNode *cur)
{
    LinkedListNode *prev = NULL;
    LinkedListNode *next;
    while (cur)
    {
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

LinkedListNode *zip_given_linked_list(LinkedListNode *head)
{
    if (head == NULL)
    {
        return NULL;
    }
    /*
    Using slow-fast technique find the middle element.
    If head: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL,
    then slow should stop at 3.
    */ 
    LinkedListNode *slow = head;
    LinkedListNode *fast = head->next;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    /*
    Separate linked lists from the middle.
    list1: 1 -> 2 -> 3 -> NULL
    list2: 4 -> 5 -> 6 -> NULL
    */
    LinkedListNode *list1 = head;
    LinkedListNode *list2 = slow->next;
    /*
    Till now:
    1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL
    With list1 pointing to 1, list2 pointing to 4 and slow pointing to 3.
    Now break main linked list into two parts.
    So do 3->next = NULL.
    */
    slow->next = NULL;
    /*
    Reverse list2 so that from
    list2: 4 -> 5 -> 6 -> NULL
    it becomes
    list2: 6 -> 5 -> 4 -> NULL
    */
    list2 = reverse_linked_list(list2);
    /*
    For readability we declare two new pointers instead of reusing
    already declared "slow" and "fast", for example.
    */
    LinkedListNode *next1;
    LinkedListNode *next2;
    /*
    Merge list1 and list2.
    list1: 1 -> 2 -> 3 -> NULL
    list2: 6 -> 5 -> 4 -> NULL
    merged: 1 -> 6 -> 2 -> 5 -> 3 -> 4 -> NULL
    */
    while (list2)
    {
        next1 = list1->next;
        next2 = list2->next;
        list1->next = list2;
        list2->next=next1;
        list1 = next1;
        list2 = next2;
    }
    return head;
}


Attend our Free Webinar on How to Nail Your Next Technical Interview

Recommended Posts

All Posts