链表翻转、合并

    今天面试遇到了链表逆序的问题，当时笔试还写错了一点，以此纠正自己，好好学习。

    逆置实现：
    点击(此处)折叠或打开

LinkList reverse(LinkList head)
{
    LinkList p = head->next;

    LinkList q = p->next;               //p为新头结点
    head->next = NULL;                  //头结点无数据，断开头结点，其他节点头插法插入

        while(p)                        //遍历查找
        {

        p->next = head->next;
        head->next = p;

       if(q)                           //判断q不为空
        {
            p = q;
            q = p->next;
        }
        else
            break;
        }

    return head;
}

    

链表操作：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef int DataType;

typedef struct node
{
    DataType data;
    struct node *next;
}LinkNode, *LinkList;

LinkList create_empty_linklist();
LinkList reverse(LinkList head);                         //链表逆序
int insert_order_linklist(LinkList head,DataType data);  //有序插入
LinkList sorted_merge(LinkList a,LinkList b);            //链表合并
int insert_head_linklist(LinkList head,DataType data);   //头插法
int insert_tail_linklist(LinkList head,DataType data);   //尾插法
int print_linklist(LinkList head);                       //链表输出
int delete_assign_node(LinkList head,DataType data);     //删除指定元素

int main()
{
   LinkList head = NULL,head2 = NULL,head3 = NULL;
   int i = 0;

   head = create_empty_linklist();

   for(i = 0; i < 10; i++)
   {
        insert_head_linklist(head,i);
     // insert_tail_linklist(head,i);
   }
    print_linklist(head);

    delete_assign_node(head,7);
    print_linklist(head);

    reverse(head);
    print_linklist(head);

    insert_order_linklist(head,7);
    print_linklist(head);

    head2 = create_empty_linklist();
    {
        insert_head_linklist(head2,23);
        insert_head_linklist(head2,7);
        insert_head_linklist(head2,4);
    }
    print_linklist(head2);

    head3 = create_empty_linklist();
    {
        insert_head_linklist(head3,12);
        insert_head_linklist(head3,8);
        insert_head_linklist(head3,5);
    }
    print_linklist(head3);

    LinkList res = sorted_merge(head2,head3);
    print_linklist(res);

   exit(0);
}

LinkList create_empty_linklist()
{
     LinkList head = NULL; //声明空结点

     head = (LinkList)malloc(sizeof(LinkNode));

     head->next = NULL; //头结点指针域为空

     return head ;
}

LinkList reverse(LinkList head)
{
    LinkList p = head->next;
    LinkList q = p->next; //分离出新的链表p
    head->next = NULL;          //断开头结点，头结点无数据，依次头插法插入到head中，实现逆置。

    while(p)
    {
        p->next = head->next;
        head->next = p;      //头插法插入结点

        if(q)
        {
            p = q;
            q = q->next;
        }
        else
            break;
    }

    return head;
}

LinkList sorted_merge (LinkList a, LinkList b)
{
    LinkList result = NULL;
#if 1
    if(a == NULL)
        return b;
    else if(b == NULL)
        return a;
#endif
    if(a->data <= b->data)
    {
        result = a;
        result->next = sorted_merge(a->next,b);
    }

    else
    {
        result = b;
        result->next = sorted_merge(a,b->next);
    }

    return result;
}

int insert_head_linklist(LinkList head,DataType data)
{
    struct node *temp = NULL;
    temp = (struct node *)malloc(sizeof(struct node));

    temp->data = data;
    temp->next = head->next; //后继
    head->next = temp; //前驱

    return 0;
}


int insert_tail_linklist(LinkList head,DataType data)
{
    struct node *temp = NULL;
    temp = (struct node*)malloc(sizeof(struct node));

    LinkList p = head;
    while(p->next) //遍历到链表尾部插入结点
    {
        p = p->next;
    }

    temp->data = data;
    temp->next = NULL;
    p->next = temp;


    return 0;
}

int insert_order_linklist(LinkList head,DataType data)
{
    struct node *temp =NULL;
    temp = (struct node *)malloc(sizeof(struct node));

    LinkList p = head;
#if 0
    while(p->next)
    {

        if(data < p->next->data)
        {
            break;
        }
        p = p->next;
    }
#endif
    while(p->next && data>p->next->data)
    {
        p = p->next;
    }
        temp->data = data;
        temp->next = p->next;
        p->next = temp;

        return 0;
}

int delete_assign_node(LinkList head,DataType data) //删除指定元素节点
{
    LinkList temp = NULL;
    LinkList p = head;

    while(p->next)
    {
        if(p->next->data == data)
        {
            break ;
        }
        p = p->next;
    }

    if(p->next == NULL) //说明节点不存在
    {
        return -1;
    }

    temp = p->next;
    p->next = temp->next;

    free(temp);

    return 0;
}

int print_linklist(LinkList head)
{
     LinkList p = head->next; //遍历链表

    while(p)
    {
        printf("%d ",p->data);
        p = p->next;
    }

    putchar('\n');

    return 0;
}

运行结果：