单链表

单链表的结构示意图

  单链表是一种顺序存储的结构. 有一个头结点,没有数据,只存储链表第一个节点的地址. 除了尾结点,每个节点都有唯一的直接后继. 所以,单链表中查询第i个元素必须知道头结点且顺序访问前i-1个结点数据才能找到.

单链表统一结构

typedef int ElementType;
typedef struct Node{
     ElementType data;
     struct Node* next;
}*ListNode;

查找单链表中倒数第k个结点

ListNode* findKth(ListNode* head, int k){
    if(head == NULL || k == 0)  //倒数第0个无意义
        return NULL;

    ListNode* p = head;
    ListNode* q = head;
    for(int i = 0;i < k - 1; i++){ //先让第一个指针走到第k个结点,如果链表不够长,直接返回空
        if(p->next != NULL)
            p = p->next;
        else
            return NULL;
    }

    while(p->next != NULL){  //p只要走到结尾,q即为倒数第k个结点
        p = p->next;
        q = q->next;    
    }

    return p;
}

合并两个有序的单链表,合并后依然有序

ListNode* Merge(ListNode* p, ListNode* q){    //采用归并的思想
    if(!p) return q;
    if(!q) return p;        //若有一个为空,返回另一个

    ListNode *r = NULL;
    ListNode *rhead = NULL;
    if(p->data < q->data){    //定下头指针
        rhead = p;
        p = p->next;
    }
    else{
        rhead = q;
        q = q->next;
    }
    r = rhead;   //r当工作指针
    while(p!=NULL && q!=NULL){    //公共部分进行有序合并
        if(p->data < q->data){
            r->next = p;
            p = p->next;
        else{
            r->next = q;
            q = q->next;
        }
    r = r->next;
    }

    if(p == NULL) r->next = q;    //公共部分跳出后,若有剩下,则直接指向剩下的头
    if(q == NULL) r->next = p;

    return rhead;
}

单链表的就地逆置(头插法)

ListNode* reverseList(ListNode* p){
    ListNode* q = p;
    ListNode* qpre = NULL;
    while(q != NULL){
        ListNode *r = q->next;         //防止断链
        q->next = qpre;        //保存尾指针
        qpre = q;         //完成一次翻转,前移
        q = r;
    }
    return qpre;
}

从尾到头打印单链表

const int maxn = 1010;        //数组无法变长,尽量设一个最大值可以容下链表结点数
void reversePrint(ListNode *head){     //原文用cpp且返回变长数组,此处仅仅只是打印,且没用std
    if(head === NULL)
        return;        //日常判空
    int print[maxn];
    int top = -1;
    while(top != -1 || head != NULL){
        print[++top] = head->data;
        head = head->next;
    }
    while(top>=0){
        printf("%d",print[top--]);
        if(top>0)
            printf(" ");
    }    
}

带环的单链表中,找到环的起始点

ListNode* meetingNode(ListNode *p){    //判断是否有环,快慢指针的方法
    if(p == NULL || p->next == NULL)
        return NULL;
    ListNode *slow = p, *fast = p;
    while(fast->next != NULL && fast->next->next !=NULL){  //一快一慢,有环必定相遇
        slow = slow->next;
        fast = fast->next->next;
        if(fast == slow)
            return fast;
    }
    return NULL;
}

ListNode* entryNode(ListNode *p){     //找到环的入口结点
    ListNode *meeting = meetingNode(p);
    if(meeting == NULL) return NULL; //无环或者空链表
    int loopNodes = 1;
    ListNOde *node = meeting;
    while(node->next != meeting){
        node = node->next;
        loopNodes++;        //计算环的长度
    }

    ListNode *head = p;
    for(int i=0;i<loopNodes;i++)
        head = head->next;

    ListNode *another = p;
    while(head != another){
        head = head->next;
        another = another->next;
    }

    return head;
}

判断两个单链表相交的第一个交点

//由于有重复操作,封装一些重复的方法还是有必要的
int getLength(ListNode *p){  //获取链表长度
    int num = 0;
    while(p!=NULL){
        p=p->next;
        num++;
    }
    return num;
}

ListNode* longMustWalk(ListNode *p,int k){    //长链必须先移到和短链一样长度的起点处
    ListNode *q = p;
    while(k>=0){
        q = q->next;
    }
    return q;
}

ListNode* findfirstCommom(ListNode* p, ListNode* q){  //找到第一个交点
    int lenp = getLength(p);
    int lenq = getLength(q);
    if(lenp>lenq) p = longMustWalk(p,len1-len2);
    else q = longMustWalk(q,len2-len1);    //让长的那一条,先走掉长-短的结点数
    while(p!=NULL && q!=NULL && p!=q){
        p = p->next;
        q = q->next;
    }

    return p;
}

删除链表中重复的结点

ListNode* delduplication(ListNode* p){        //重复的全部删掉,不保留
    if(p == NULL || p->next == NULL)
        return p;
    ListNode* q = (ListNode*)malloc(sizeof(struct Node));
    q->data = -1;
    q->next = p;        //此处为若头结点被删除的处理
    ListNode *pre = q, *r = p, *next = NULL;
                //对应前驱,工作指针,next指针
    while(r!=NULL && r->next != NULL){
        next = r->next;
        if(r->val == next->val){
            while(next != NULL && r->val == next->val)
                next = next->next;    
            pre->next = next;
            r = next;
        }
        else{
            pre = r;
            r = next;
        }
    }
    return q->next;            //返回的是有带头结点的
}

阅读原文