将两个递增的双向链表合并问题

Question

将两个排好序的双向链表合并成一个，不允许有重复数据，链表1为1 2 3 4 6
链表2为5 6 8 9 10，合并后为1 2 3 4 6 8 9 10缺少了5，麻烦各位看一下是为什么啊？

// shiyan.cpp : 定义控制台应用程序的入口点。
//
/* C program to insetail nodes in doubly 
linked list such that list remains in 
ascending order on printing from left 
to right */
#include "stdafx.h"
#include <iostream>
using namespace std;
#include<stdio.h> 
#include<stdlib.h> 
#include<fstream>

// A linked list node 
struct Node 
{  
    int data; 
    struct Node *prior; 
    struct Node *next; 
}; 
// Function to insetail new node 
void nodeInsetail(struct Node **head, struct Node **tail,int key) 
{ 
    struct Node *p = new Node; 
    p->data = key; 
    p->next = NULL; 
    // If first node to be insetailed in doubly linked list 
    if ((*head) == NULL) 
    { 
        (*head) = p; 
        (*tail) = p; 
        (*head)->prior = NULL; 
        return; 
    } 
    // If node to be insetailed has value less than first node 
    if ((p->data) < ((*head)->data)) 
    { 
        p->prior= NULL; 
        (*head)->prior = p; 
        p->next = (*head); 
        (*head) = p; 
        return; 
    } 
    // If node to be insetailed has value more than last node 
    if ((p->data) > ((*tail)->data)) 
    { 
        p->prior = (*tail); 
        (*tail)->next = p; 
        (*tail) = p; 
        return; 
    } 
    // Find the node before which we need to insert p. 
     struct Node *temp = new Node; 
     temp = (*head)->next; 
     while ((temp->data) < (p->data)) 
        temp = temp->next; 
    // Insert new node before temp 
    (temp->prior)->next = p; 
    p->prior= temp->prior; 
    temp->prior = p; 
    p->next = temp; 
} 

// Function to print nodes in from left to right 
void printList(struct Node *temp) 
{ 
    while (temp != NULL) 
    { 
        printf("%d ", temp->data); 
        temp = temp->next; 
    } 
} 

// Driver program to test above functions 
struct Node *head1=NULL;
struct Node *tail1=NULL;
struct Node *head2=NULL;
struct Node *tail2=NULL;

int _tmain(int argc, _TCHAR* argv[])
{
    int num[10];
    int datalen=0;
    ifstream file("linklist.txt");
    while( ! file.eof() )
    file>>num[datalen++];
    file.close();
    for(int i=0;i<5;i++)
    {
        nodeInsetail(&head1, &tail1,num[i]); 
    }
    printf("Doubly linked list1 is:"); 
    printList(head1);
    printf("\n");
    for(int j=5;j<10;j++)
    {
        nodeInsetail(&head2, &tail2,num[j]); 
    }
    printf("Doubly linked list2 is:"); 
    printList(head2);
    printf("\n");

    Node *phead =head1;//最终返回的头数据节点
    Node *p=head1->next;//p循环的是链表1
    Node *q=head2;//q循环的是链表2
    if(p->data > q->data)
    {
        phead = head2;
        p = head2->next;
        q = head1;
    }
    Node* s=phead;//记录新链表的最后一个节点，方便下一次接上新节点
    while(p!=NULL && q!=NULL)
    {
        if(p->data < q->data)
        {
            s->next = p;
            p->prior=s;
            p = p->next;
            s = s->next;
        }
        else if(p->data = q->data)
        {
            s->next= p;
            p->prior=s;
            p=p->next;
            Node *x=q->next;//备用元素指向
            free(q);
            q=x;
        }
        else if(p->data > q->data)
        {
            s->next = q;
            q->prior=s;
            q = q->next;
            s = s->next;
        }
    }
    if(p == NULL)//链表1先遍历完，说明另一链表还有数据得接过来
    {
        s->next = q;
        q->prior=s;
    }
    if(q == NULL)//链表2先遍历完，因为此时主链表的结构已经发生变化，所以仍需拼接过来
    {
        s->next = p;
        p->prior=s;
    }
    while(phead)
     {
     printf("%d ",phead->data);
     phead=phead->next;
     }
    return 0;
}

Answer 1

    Node* phead, * p, * q, * s, * t;
    if (head1->data > head2->data) {
        phead = head2;
        q = head1;
    }
    else {
        phead = head1;
        q = head2;
    }
    p = phead;
    s = phead;
    while (p != NULL && q != NULL)
    {
        if (p->data < q->data)
        {
            s = p;
            p = p->next;
        }
        else if (p->data == q->data)
        {
            q = q->next;
            if (q)
                free(q->prior);
            else
                break;
        }
        else
        {
            t = q->next;
            p->prior->next = q;
            q->prior = p->prior;
            q->next = p;
            p->prior = q;
            q = t;
        }
    }
    if (p == NULL)
    {
        s->next = q;
        q->prior = s;
    }
    while (phead)
    {
        printf("%d ", phead->data);
        phead = phead->next;
    }
    return 0;