Back to Front Linked List - Amazon Top Interview Questions

                        Solution in C++ :

LLNode* solve(LLNode* node) {
    LLNode* slow = node;
    LLNode* fast = node;
    while (fast) {
        fast = fast->next;
        if (fast) {
            fast = fast->next;
            slow = slow->next;
        }
    }
    LLNode* pre = NULL;
    LLNode* cur = slow;
    LLNode* nex;
    while (cur) {
        nex = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nex;
    }
    LLNode* temp = pre;
    while (temp && node) {
        LLNode* nex1 = temp->next;
        LLNode* nex2 = node->next;
        temp->next = node;
        node->next = nex1;
        temp = nex1;
        node = nex2;
    }
    return pre;
}
                    

                        Solution in Java :

import java.util.*;

/**
 * class LLNode {
 *   int val;
 *   LLNode next;
 * }
 */
class Solution {
    public LLNode solve(LLNode node) {
        LLNode fast = node, slow = node;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        LLNode left = node, right = reverse(slow);
        LLNode prev = new LLNode();
        LLNode dummy = prev;
        while (left != null && right != null) {
            prev.next = right;
            right = right.next;
            prev.next.next = left;
            left = left.next;
            prev = prev.next.next;
        }
        prev.next = null;
        return dummy.next;
    }

    private LLNode reverse(LLNode node) {
        LLNode prev = null, curr = node, next;
        while (curr != null) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def split(self, head):
        tail1 = head
        tail2 = head

        while tail1 and tail2 and tail2.next and tail2.next.next:
            tail1 = tail1.next
            tail2 = tail2.next.next

        # now actually break the link!
        head2 = tail1.next
        tail1.next = None

        return head, head2

    def reverse(self, head):
        if not head or not head.next:
            return head
        prev, cur = None, head
        while cur:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt

        return prev

    def interleave(self, head, head2):
        resHead = res = LLNode(0)
        while head or head2:
            if head2:
                res.next = head2
                res = res.next
                head2 = head2.next

            if head:
                res.next = head
                res = res.next
                head = head.next

        return resHead.next

    def solve(self, head):
        # break into two halves
        head, head2 = self.split(head)

        # now reverse the second list ;)
        head2 = self.reverse(head2)

        # just alternately pick from each
        return self.interleave(head, head2)