連結清單的C++實作（查找中間節點、判斷是否存在環）

1、連結清單的實作

struct Node {
    int data;
    Node *next;
};

class Link {
public:
    Node *root;
    Link()
    {
        root = new Node;
    }
    /*
     Create
     *函數功能：建立連結清單.
     *輸入：各節點的data
     *傳回值：指針head
     */
    Node *create() //*&是指針的引用
    {
        Node *p1,*p2 = nullptr;
        Node *head=NULL;
        
        cout<<"輸入數序(以負數或0結束): ";
        int n;
        cin>>n;
        while(n>0)
        {
            p1=new Node;
            p1->data=n;
            p1->next=NULL;
            if(NULL==head){               //将head, p1, p2都指向頭結點
                head=p1;
                p2=head;
            }else{
                p2->next=p1;
                p2=p1;
            }
            cin>>n;
        }
        root = head;
        return root;
    }
    
    
    /*
     insert
     *函數功能：在連結清單中插入元素.
     *輸入：head連結清單頭指針，p新元素插入位置，x新元素中的資料域内容
     *傳回值：無
     */
    Node *insert(Node *head, int p, int x)
    {
        cout<<"在第"<<p<<"元素後插入"<<x<<endl;
        Node *tmp=head;//for循環是為了防止插入位置超出了連結清單長度
        for(int i=0; i<p;i++)
        {
            if(tmp==NULL){
                return head;
            }
            if(i<p-1){
                tmp=tmp->next;
            }
        }
        Node *tmp2=new Node;
        tmp2->data=x;
        tmp2->next=tmp->next;
        tmp->next=tmp2;
        return head;
    }
    
    /*
     del
     *函數功能：删除連結清單中的元素
     *輸入：head連結清單頭指針，p被删除元素位置
     *傳回值：被删除元素中的資料域.如果删除失敗傳回-1
     */
    int del(Node *head,int p)
    {
        Node *tmp = head;
        for(int i=1;i<p;i++)
        {
            if(tmp==NULL)
                return -1;
            if(i<p-1){
                tmp=tmp->next;
            }
        }
        int ret=tmp->next->data;
        tmp->next=tmp->next->next;
        return ret;
    }
    // 求連結清單長度
    int len(){
        return len(root);
    }
    int len(Node *h)
    {
        int i=0;
        while(h!=NULL)
        {
            i++;
            h=h->next;
        }
        return i;
    }
    
    /*
     驗證連結清單是否有環，如：1->2->3->4->6->5
                             ↑———8<———│
     有傳回1,否則傳回0
     */
    int checkCircle(Node *head)
    {
        if (head == NULL) return 0;
        Node *p = head;
        Node *q = head->next;
        while ( q!=NULL) {
            if (q == p) return 1;
            p = p->next;
            if (q->next == NULL) return 0;
            else q = q->next->next;
        }
        return 0;
    }
    
    int checkCircle2(Node* head)
    {
        if (head == NULL) return 0;
        Node *p = head;
        Node *q = head->next;
        if (q == p) return 1;
        
        while (p->next) {
            p = p->next;
            q = head;
            while (q!=p) {
                if (q == p->next) {
                    cout<<"The data of circle Node is "<<p->data<<endl;
                    return 1;// 此時q所在的節點就是拆分節點
                }
                q = q->next;
            }
        }
        return 0;
    }
    
    /*
     findMidElement
     *函數功能：查找連結清單中的中間元素
     *輸入：head連結清單頭指針，p被删除元素位置
     *傳回值：被中間節點元素中的資料域.如果沒有傳回NULL
     */
    Node *findMidElement(){
        return findMidElement(root);
    }
    
    Node *findMidElement (Node *head){
        if (head == NULL) return NULL;
        Node *mid = head;
        Node *p = head->next;
        while (p!=NULL) {
            if (p != mid) {
                mid = mid->next;
            }
            if (p->next != NULL){
                p = p->next->next;
            }
        }
        cout<<"the middle of node's data is "<<mid->data<<endl;
        return mid;
    }
    
    //列印節點
    void display(){
        if (!checkCircle(root)) {
            display(root);
        }else{
            cout<<"The circle Link!"<<endl;
        }
    }
    void display(Node *head)
    {
        for(Node*tmp=head;tmp!=NULL;tmp=tmp->next){
            printf("%d->",tmp->data);
        }
        printf("\n");
    }
};
           

2、查找連結清單的中間節點

Node *findMidElement (Node *head){
        if (head == NULL) return NULL;
        Node *mid = head;
        Node *p = head->next;
        while (p!=NULL) {
            if (p != mid) {
                mid = mid->next;
            }
            if (p->next != NULL){
                p = p->next->next;
            }
        }
        cout<<"the middle of node's data is "<<mid->data<<endl;
        return mid;
    }

           

3、檢測連結清單是否有環

• 方法一：更加查找中間節點的思路 —— 缺點無法具體知道從哪個點

int checkCircle1(Node *head)
{
    if (head == NULL) return 0;
    Node *p = head;
    Node *q = head->next;
    while ( q!=NULL) {
		if (q == p) return 1;
        p = p->next;
        if (q->next == NULL) return 0;
        else q = q->next->next;
    }
    return 0;
}

           

• 方法二：用兩個連結清單指針p,q, 從頭節點開始查找。 p一直往後找。p每查找一個節點，q都從頭節點一直往後找到q相等的節點，查找過程中如果p的下一個節點剛好是q說明有環。

int checkCircle2(Node* head)
{
	if (head == NULL) return 0;
    Node *p = head;
    Node *q = head->next;
	if (q == p) return 1;

    while (p->next) {    
        p = p->next;
        q = head;
        while (q!=p) {
            if (q == p->next) return 1;// 此時q所在的節點就是拆分節點
            q = q->next;
        }
    }
    return 0;
}
           

驗證

int main(int argc, const char * argv[]) {
    Link link;
    link.create();
    link.display();
    
    link.insert(link.root, 2, 3);
    link.display();
    
    Node *mid = link.findMidElement(link.root);
    mid->next = link.root;
    link.display();

    return 0;
}