C++

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int h = -1, ne[N], e[N];
int address[N];     //given val, access address quickly


int L1, L2, n;

int get_len(int head)
{
    int res = 0;
    while (head != -1) {
        head = ne[head];
        res++ ;
    }
    return res;
}

int rev_list(int head)
{
    int p = head, temp = -1;
    while (p != -1) {
        int ne_ars = ne[p];
        ne[p] = temp;
        temp = p;
        p = ne_ars;
    }
    return temp;
}

void merge_list(int h1, int h2)
{
    int i = h1, cnt = 0;
    int k = h2;
    while (i != -1) {
        cnt = (cnt + 1) % 2;        //judge whether there should merge node
        if (!cnt and k != -1) {     //cnt==0, and k still have nodes, it's time to merge
            int tempi = ne[i], tempk = ne[k];
            ne[i] = k, ne[k] = tempi;
            i = tempi, k = tempk; 
        }
        else {    //normally traverse, the forward merging steps illustrate why i don't use for loop here
            i = ne[i];
        }
    }
}

void print_list(int head);  //help function used in debug

int main()
{
    scanf("%d%d%d", &L1, &L2, &n);
    for (int i = 0; i < n; i++ ) {
        int ars, val, nev; scanf("%d%d%d", &ars, &val, &nev);
        e[ars] = val, ne[ars] = nev;
        address[val] = ars; 
    }
    int len1 = get_len(L1), len2 = get_len(L2);
    if (len1 < len2) swap(L1, L2);      //make sure L1 is always the larger linked list

    L2 = rev_list(L2);      
    //print_list(L2);
    merge_list(L1, L2);     //reverse L2 and merge L1 and L2
    //print_list(L1);

    int cnt = 0;
    for (int i = L1; i != -1; i = ne[i]) {      //print merged list begin with L1
        if (cnt) puts("");
        cnt++;
        int val = e[i], ne_ars = ne[i];
        if (ne_ars != -1) {
            printf("%05d %d %05d", i, val, ne_ars);
        }
        else {
            printf("%05d %d %d", i, val, ne_ars);
        }
    }
    return 0;
}

void print_list(int head)
{
    for (int i = head; i != -1; i = ne[i]) {
        cout << e[i] << " ";
    }
    cout << endl;
}