算法-链表合集

1.

void Del(LinkList *L，int x){
    LinkList *p = L->next;
    LinkList *pre = L;
    LinkList *temp;
    while(p != null){
        if(p ->data == x){
            temp = p;//temp指向被删节点
            p=p->next;
            pre->next = p;
            free(temp);
        }else{
            pre = p;
            p = p->next;
        }
    }
}

其中的if(p ->data == x)可以被替换为任何条件

2.

void Del(LinkList *L){
    LinkList *p = L->next;
    LinkList *pre = L;
    LinkList *minpre = pre,*minp = p;   //最小指针前驱以及最小指针
    while(p != null){
        if(p->data < minp->data){
            minp = p ;
            minp = pre;
        }
        pre = p ;
        p = p ->next;
    }
    minpre->next = minp->next;
    free(minp);
}

3.

void Reverse(LinkList *L){
    LinkList * r = null;//p为工作指针，r为p的后继指针
    LinkList *p = L->next;
    L->next = null;
    while(p != null){
        r = p->next;
        p->next = L->next;
        L->next = p;
        p = r;
    }//这里使用头插法建立单链表
}

4.

1的变种

5.

找出两个链表的公共结点，应遵循**“若有一个公共结点，那么他们的最后一个结点必定是重合的”**。根据这一思路中，我们先要分别遍历两个链表得到它们的长度，并求出两个长度之差。在长的链表上先遍历长度之差个结点之后，再同步遍历两个链表，直到找到相同的结点，或者一直到链表结束。此时，该方法的时间复杂度为 O（lenl + len2）。

6.

7. 略

void GetCommon(LNode *a,LNode *b,LNode *c){
    c = (LNode*)malloc(sizeof(LNode));
    LinkList pa=a->next,pb=b->next;
    LinkList r = c;     //尾插法，r始终指向尾节点
    while(pa != null && pb!= null){
        if(pa->data == pb->data){
			temp=(LNode*)malloc(sizeof(LNode));
			r->next = s;    //1
            r=s;        //2
			temp->data = pa->data;
            pa = pa->next;
			pb = pb->next;
		}else{
			if(pa->data > pb->data){
				pb = pb->next;
			}
			if(pa->data < pb->data){
				pa = pa->next;
			}
		}
    }
    r->next = null;//使用尾插法时，记得最后将尾指针置空
}

尾插法

9. 略

int pattern(LNode *a,LNode *b){
    LNode *pa = a;
    LNode *pb = b;
    LNode *pre = pa;
    while(pa != null && pb != null){
        if(pa->data == pb->data){
            pa = pa->next;
            pb = pb->next;
        }else{
            pre = pre->next;
            pa = pre->next;
            pb = b;
        }
    }
    if(pb == null){
        return 1;//匹配成功
    }else{
        return 0;
    }
}

11.

int Symmetry(LNode *L){
    LinkList p = L->next;
    LinkList q = L->prev;
    while(p!=q || q->next != p){    //不要写成p->next != q
        if(p->data != q->data){
            return 0
        }
    }
    return 1;
}

12.

LNode Link(LNode *h1,LNode *h2){
    LinkList ph1 = h1;//工作指针
    LinkList ph2 = h2;//工作指针
    while(ph1->next != h1){
        ph1 = ph1->next;
    }
    while(ph2->next != h2){
        ph2 = ph2->next;
    }
    ph1->next = h2;
    ph2->next = h1;
}

LNode *Converse(LNode *L,int k){
    int count = 0;
    LinkList p = L;
    while(p->next != null){
        p = p ->next;
        count++;
    }
    p->next = L;
    while(int i = 0 ;i<n-k;i++){
        p = p->next;
    }//找到新头结点的前一个结点
    L = p->next;
    p->next = null;//断环
    return L;
}

15. 判断链表是否成环

int isCircle(LNode *L){
    LinkList fast = L,slow=L;
    while(fast != null || fast->next != null){
        slow = slow ->next;
        fast = fast ->next->next;
        if(fast == slow){
            break;
        }
    }
}