链表常见操作

面试常会考到链表和C库函数的操作,特地整理下了链表的常用函数,以供参考:
一.链表
链表定义如下:
为了程序的可读性,LinkList表示链表头节点指针,用于表示一个链表,pNode表示节点指针

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

typedef struct Node
{
    int data;
    struct Node *next;
}Node,*LinkList,*pNode;
//为了简单起见,我们讲链表值保存到一个数组中,这样链表操作后可以显而易见的看到运行结果是否正确.
int LinkListData[10] = {0,1,2,3,4,5,6,7,8,9};

另外我们创建的链表是带头结点的链表,即单链表的首元结点(存放第一个数据元素的结点)之前附设一个头结点(数据域什么都不放),称之为带头结点的单链表，反之就是不带头结点的单链表。

1.创建链表
(1)顺序创建链表
p是临时节点指针,指向最后一个节点.增加一个节点时实际上就是在链表尾部插入一个新节点.

LinkList CreateListSequence(int num)
{
    pNode p,pHead,pEnd;
    int i;
    if(!(p = pHead = (LinkList)malloc(sizeof(Node))))
    {
        return NULL;
    }
    p->next = pHead->next = NULL;
    for(i=0;i<num;i  )
    {
        if(pEnd = ((LinkList)malloc(sizeof(Node))))
        {
            pEnd->data = LinkListData[i];
            pEnd->next = p->next;
            p->next = pEnd;
            p = pEnd;
        }
    }
    return pHead;
}

(2)逆序创建链表
逆序创建链表时就是将新的节点(pNew)插入到Head节点之后.

LinkList CreateListInverse(int num)
{
    LinkList pHead,pNew;
    int i;

    if(!(pHead=(LinkList)malloc(sizeof(Node))))
    {
        return NULL;
    }
    pHead->next = NULL;
    for(i=0;i<num;i  )
    {
        if(pNew=(LinkList)malloc(sizeof(Node)))
        {
            pNew->data = LinkListData[i];
            pNew->next = pHead->next;
            pHead->next = pNew;
        }
    }
    return pHead;
}

2.获取某个指定结点的值

int GetElement(LinkList list,int location)
{
    int i = 0;
    pNode point = list->next;
    while(point && i<location)
    {
        point = point->next;
        i  ;
    }
    if(!point || i > location)
        return 0;
    return point->data;
}

3.插入元素

int ListInsert(LinkList list,int location,int arg)
{
    pNode point=list->next,node;
    int i=1;
    while(i<location)
    {
        point = point->next;
        i  ;
    }
    if(!point || (i > location))
    {
        printf("/nInsert operatoin failed");
        return 0;
    }
    if(!(node =(LinkList)malloc(sizeof(Node))))
        return 0;
    node->data = arg;
    node->next = point->next;
    point->next = node;

    return 1;
}

4.删除元素

void ListDelete(LinkList list,int location)
{
    LinkList point = list->next;
    int i = 1;
    while(i < location)
    {
        point = point->next;
        list = list->next;
        i  ;
    }
    if(!point || (i > location))
    {
        printf("/nDelete operation failed!/n");
        return;
    }
    list->next = point->next;
    free(point);
}

5.反序链表
最简单就是前插法,将头结点摘下来,然后采用前插法依次插入,例如:
初始：      head   ->   1   ->   2   ->   3 
第一步：   head 
第二步：   head   ->   1 
第三步：   head   ->   2   ->   1 
第四步：   head   ->   3   ->   2   -> 1 

LinkList ReverseLinkList(LinkList pHead)
{
    pNode p = pHead-> next;

    pHead->next = NULL;

    while(p){
        pNode q=p;
        p = p-> next;
        q->next = pHead-> next;
        pHead->next = q;
    }

    return pHead;
}

6.找出链表中间节点
采用两个节点指针,一个一次移动2个节点,一个一次移动一个节点,这样只需偏历一次链表就可以找到中间节点了.

Node* find_midlist(LinkList pHead)
{
    pNode p1, p2;
    if(pHead == NULL || pHead->next == NULL)
        return pHead;
        //链表有头结点,如无头结点,则为p1 = p2 = pHead->next
    p1 = p2 = pHead->next;
    while (1)
    {
        if (p2->next != NULL && p2->next->next != NULL)
        {
            p2 = p2->next->next;

            p1 = p1->next;
        }
        else
        {
            break;
        }
    }
    return p1;
}

7.判断一个单链表是否有环
这道题是《C专家编程》中的题了.这里采用的算法是一个指针一次走一步,另一个一次走两步,如果链表有环,那么这两个指针一定会相遇.

int is_looplist (LinkList pHead)
{
    pNode p1, p2;

    p1 = p2 = pHead;

    if (pHead == NULL || pHead->next == NULL)
        return 0;
    while (p2->next != NULL && p2->next->next != NULL)
    {
        p1 = p1->next;
        p2 = p2->next->next;

        if (p1 == p2)
           return 1;
    }
    return 0;
}