《剑指offer》第二章小结（1）——链表的基本操作

《剑指offer》第二章小结（1）——链表的基本操作

面试题5是从尾到头打印链表，与此相关的链表的基本操作应该知道。
下面代码中列举了单链表的创建、遍历、插入和删除四种操作。参考网址：
http://blog.csdn.net/jamie321/article/details/52369634
http://blog.csdn.net/i_am_what_i_am/article/details/51532371

//链表结点的定义，注意：本文的链表的第一个结点均是不存储有效数据的头结点
typedef struct ListNode {
    int val;
    struct ListNode* next;
}Node;
Node* CreateList();                 //创建链表函数  
void TraverseList(Node* );          //遍历链表函数  
bool Insert_Head(Node* pHead,int data);//头插法
bool Insert_Tail(Node* head,int data); //尾插法
bool Insert_mid(Node* head,int n,int data);//在链表中插入
bool Del_Node(Node* ,int); //删除链表节点,第一个参数是头节点，第二个参数是删除第几个节点

//创建链表，返回头结点
Node* CreateList() {  
    int i;                                          //用于下面循环  
    int len;                                        //用来存放有效节点的字数  
    int val;                                        //用于临时存放用户输入的数据  
    Node* pHead = (Node*)malloc(sizeof(Node));      //分配一个不存放有效数据的头结点  
    Node* pTail = pHead;                            //链表的最后一个节点  
    pTail->next = NULL;                             //最后一个节点的指针置为空  
    printf("请输入节点个数：");  
    scanf("%d",&len);  
    for(i = 0; i < len; i++) {  
        printf("第 %d 个节点的数值：",i+1);  
        scanf("%d",&val);  
        Node* pNew = (Node* )malloc(sizeof(Node));  //为结点分配空间  
        pNew->val = val;           //将用户输入的数据赋给新节点的成员   
        pNew->next = NULL;         //将新结点中的指针置为空
        pTail->next = pNew;        //新结点入链表，将最后一个结点的指针指向下一个新的节点   
        pTail = pNew;              //新结点称为最后一个结点将新节点赋给最后的一个结点  
    }  
    return pHead;                                   //返回头节点  
}  

//遍历链表函数
void TraverseList(Node* pHead) {  
    Node* p = pHead->next;                          //将头节点的指针给予临时节点p  
    while(p != NULL) {                              //节点p不为空，循环        
        printf("%d ",p->val);                      
        p = p->next;                                  
    }  
    printf("\n");  
    return ;  
} 

//头插法
bool Insert_Head(Node* pHead,int data) { //链表的头结点不存储有效数据，
    Node *p;                      //实际上插入的位置是链表中的第二个结点 
    p=(Node*)malloc(sizeof(Node));
    if(pHead == NULL || p == NULL)//若头结点地址为空
        return false;             //或新分配的节点地址为空，则插入失败
    p->val=data;
    p->next=head->next;
    head->next=p;
    return true;
}

//尾插法
bool Insert_Tail(Node* head,int data) {
    if(head == NULL) 
        return false; //头结点为空插入失败
    Node *p,*t=head;  //p指向新分配的结点，t做循环变量使用
    while(t->next!=NULL){
        t=t->next;
    }
    p=(Node *)malloc(sizeof(Node));
    if(p == NULL)
        return false;
    p->val=data;
    t->next=p;
    p->next=NULL;
    return true;
} 

//在链表中插入结点
bool Insert_mid(Node* head,int n,int data) { //插入值为data的结点，
    if(head == NULL)                 //使其成为除头结点外的第n个结点
        return false;
    Node *p，*t=head;
    while(--n>0){//要认真查数！
        if(t == NULL)
            return false;  
        t=t->next;     
    }//循环结束后，t指向链表中除头结点外的第n-1个结点 
    p=(Node*)malloc(sizeof(Node));
    if(p == NULL)
        return false;
    p->val=date;
    p->next=t->next；//把结点p插入到了t的后面
    t->next=p; 
    return true;
}    

//在链表中删除结点
bool Del_node(Node* head,int n) { //删除链表中除头结点外的第n个结点
    if(head == NULL)
        return false;
    Node *p，*t=head;
    while(--n>0){//要认真查数！
        if(t == NULL)
            return false;  
        t=t->next;     
    }//循环结束后，t指向链表中除头结点外的第n-1个结点 
    if(t->next == NULL)
        return false;//第n个结点不存在
    Node* del=t->next;
    t->next=t->next->next;
    free(del); 
    return true;
}