數(shù)據(jù)結(jié)構(gòu)｜有關(guān)鏈表的練習(xí)題

鏈表定義

typedef struct LNode{
    int data;
    LNode* next;
}LNode, *LinkList;

有關(guān)鏈表的一些基礎(chǔ)函數(shù)

typedef struct LNode{
    int data;
    LNode* next;
}LNode, *LinkList;

// 循環(huán)雙鏈表
typedef struct DNode{
    int data;
    DNode* prior;
    DNode* next;
}DNode, *DLinkList;

void Init(LinkList &L){
    L = (LinkList)malloc(sizeof(LNode));
    LNode* p;
    LNode *r = L;
    for(int i = 0; i < 8; i++){
        p = (LNode*)malloc(sizeof(LNode));
        if(i <= 3)
            p->data = i;
        else
            p->data = 8-1-i;
        r->next = p;
        r = p;
    }
    r->next = NULL;
}


void PrintList(LinkList L){
    LNode* p = L->next;
    while(p != NULL){
        cout<<p->data<<" ";
        p = p->next;
    }
    cout<<endl;
}

// 利用頭插法逆置
void Reverse(LinkList& L){
    LNode* p = L->next;
    L->next = NULL;
    LNode* r = L;
    while(p != NULL){
        r = p->next;  // 暫存p的下一個(gè)指針
        L->next = p;
        p->next = L->next;
        p= r;
    }
}

// 法2 設(shè)置3個(gè)指針逆置
Linklist reserve(LinkList L)
{
　　LNode *pre,*p=L->next,*r=p->next;
　　p->next=NULL;//處理第一個(gè)結(jié)點(diǎn)
　　while(r!=NULL)//r為空，則說明p為最后一個(gè)結(jié)點(diǎn)

　　{
　　　　pre=p;//依次遍歷
　　　　p=r;
　　　　r=r->next;
　　　　p->next=pre;//指針反轉(zhuǎn)
　　}
　　L->next=p;//處理最后一個(gè)結(jié)點(diǎn)
　　return L;
}

int Length(LinkList L){
    LNode *p = L->next;
    int res = 0;
    while(p != NULL){
        res++;
        p = p->next;
    }
    return res;
}
  1. 給定兩個(gè)單鏈表，找出兩個(gè)鏈表的公共結(jié)點(diǎn)。
    如果有公共結(jié)點(diǎn)，則兩個(gè)鏈表一定是Y形重合，而不是X，因?yàn)槊總€(gè)結(jié)點(diǎn)都只有一個(gè)next域，所以只要最后一個(gè)結(jié)點(diǎn)重合，那么這兩個(gè)鏈表就有公共結(jié)點(diǎn)。但是兩個(gè)鏈表的長度不一定一樣，所以遍歷的時(shí)候做不到同步，假設(shè)長鏈表比短鏈表多k個(gè)元素，那么就可以先遍歷長鏈表k步，然后再一起遍歷，做到同步。
LinkList FindCommon(LinkList L1, LinkList L2){
    int len1 = Length(L1);
    int len2 = Length(L2);
    int dist = 0;
    LinkList longlist, shortlist;
    if(len1 > len2){
        dist = len1-len2;
        longlist = L1->next;
        shortlist = L2->next;
    }
    else{
        dist = len2 - len1;
        longlist = L2->next;
        shortlist = L1->next;
    }
    while(dist--){
        longlist = longlist->next;
    }
    while(longlist != NULL){
        if(longlist == shortlist)
            return longlist;
        else{
            longlist = longlist->next;
            shortlist = shortlist->next;
        }
    }
    return NULL;
}
  1. 有一個(gè)帶頭結(jié)點(diǎn)的單鏈表L，給其排序使元素遞增
    插入排序的思想，首先構(gòu)建只有一個(gè)結(jié)點(diǎn)的鏈表，然后遍歷剩下的元素，插入排序。
LNode* Sort(LinkList& L){
    LNode* p = L->next;
    LNode* pre;
    LNode* r = p->next;
    p->next = NULL;  // 只有第一個(gè)結(jié)點(diǎn)
    p = r;  // 從p的下一個(gè)結(jié)點(diǎn)開始遍歷
    while(p != NULL){
        r = p->next;  // 保存p的后繼，避免之后被覆蓋，因?yàn)閜還要迭代
        pre = L;  // pre代表已排好序的鏈表，從一開始找到p插入的位置
        while(pre->next != NULL && pre->next->data < p->data){
            pre = pre->next;
        }
        p->next = pre->next;  // pre作為前驅(qū)，將p放在pre后面
        pre->next = p;
        p = r;  // 迭代
    }
    return L->next;
}
  1. 給定鏈表，x值，y值，刪掉鏈表當(dāng)中介于x和y之間的結(jié)點(diǎn)
void Del_xy(LinkList& L, int x, int y){
    LNode *p = L->next;
    LNode *pre = L;
    LNode* q;
    while(p != NULL){
        if(p->data > x && p->data < y){
            q = p;
            pre->next = p->next;
            free(q);
        }
        pre = pre->next;
        p = p->next;
    }
}
  1. 給定帶頭結(jié)點(diǎn)的單鏈表，head為頭指針，按遞增次序輸出單鏈表中各結(jié)點(diǎn)的數(shù)值，并釋放結(jié)點(diǎn)所占空間（不允許用數(shù)組作為輔助空間）。
    法1: 先對鏈表排序，然后輸出
    法2: 每次遍歷找到最小值，然后輸出并釋放，直到鏈表為空。
void Min_Del(LinkList &head){
    LNode *p = head->next;
    while(head->next != NULL){
        // 接下來這三步初始化很重要
        LNode *min_pre = head; // 最小元素的前驅(qū)
        int minn = head->next->data;  // 記錄最小元素
        p = head->next;  // 每次從頭開始遍歷
        while(p->next != NULL){
            if(p->next->data < minn){
                minn = p->next->data;
                min_pre = p;  // 最小元素的前驅(qū)
            }
            p = p->next;
        }
        LNode *min_p = min_pre->next;
        min_pre->next = min_p->next;
        cout<<min_p->data<<" ";
        free(min_p);
    }
    cout<<endl;
    free(head);  // 釋放掉頭結(jié)點(diǎn)
}
  1. 將一個(gè)帶頭結(jié)點(diǎn)的單鏈表A分解為兩個(gè)帶頭結(jié)點(diǎn)的單鏈表A和B，使得A中含有原表中序號為奇數(shù)的元素，B中含有原表中序號為偶數(shù)的元素，且相對順序不變。
    把A置空，給B分配空間，分別利用尾插法構(gòu)建鏈表。最后一定要記著將尾結(jié)點(diǎn)的next置空。
void Seperate(LinkList& A, LinkList& B){
    B = (LinkList)malloc(sizeof(LNode));  // 分配空間
    B->next = NULL;  // 尾結(jié)點(diǎn)置空
    int i = 0;  // 用于計(jì)數(shù)
    LNode* p = A->next;  // 存儲A的下一個(gè)元素
    A->next = NULL;  // A表尾結(jié)點(diǎn)置空
    LNode* q = B;  // q作為B的尾結(jié)點(diǎn)
    LNode* ra = A;  // ra作為A的尾結(jié)點(diǎn)
    while(p != NULL){
        if(i % 2 == 0){
            LNode* new_node = (LNode*)malloc(sizeof(LNode));
            new_node->data = p->data;
            new_node ->next = NULL;
            q->next = new_node;
            q = new_node;  // 更新尾指針
        }
        else{
            LNode* new_node = (LNode*)malloc(sizeof(LNode));
            new_node->data = p->data;
            new_node ->next = NULL;
            ra->next = new_node;
            ra = new_node;
        }
        p = p->next;
        i++;
    }
    ra->next = NULL;  // 最后的尾結(jié)點(diǎn)置空
    q->next = NULL;
}
  1. A和B是兩個(gè)遞增的單鏈表，用他們的公共元素產(chǎn)生單鏈表C，不破壞A，B中的元素。
LinkList Union_Merge(LinkList L1, LinkList L2){
    LNode *p =L1->next;
    LNode *q = L2->next;
    LinkList C;
    C = (LinkList)malloc(sizeof(LNode));
    C->next = NULL;
    LNode* r = C;  // 記錄C的尾指針
    while(p != NULL && q != NULL){
        if(p->data < q->data)
            p = p->next;
        else if(p->data > q->data)
            q = q->next;
        else{
            LNode* new_node = (LNode*)malloc(sizeof(LNode));
            new_node->data = p->data;
            r->next = new_node;
            r = new_node;
            p = p->next;
            q = q->next;
        }
    }
    r->next = NULL;
    return C;
}
  1. A,B是兩個(gè)遞增的單鏈表，求A與B的公共元素集合，并放入A鏈表中
void Find_Common(LinkList A, LinkList B){
    LNode *p = A->next;
    LNode *ra = A;  // 用來構(gòu)建新的A表
    A->next = NULL;
    LNode *q = B->next;
    while(p != NULL && q != NULL){
        if(p->data < q->data)
            p = p->next;
        else if(p->data > q->data)
            q = q->next;
        else{
            LNode* new_node = (LNode*)malloc(sizeof(LNode));
            new_node->data = p->data;
            ra->next = new_node;
            ra = new_node;
            p= p->next;
            q = q->next;
        }
    }
    ra->next = NULL;
}
  1. 對于鏈表中data的絕對值相等的結(jié)點(diǎn)，僅保留第一次出現(xiàn)的結(jié)點(diǎn)，而刪除其余絕對值相等的結(jié)點(diǎn)。
    用一個(gè)輔助數(shù)組記錄
void Del_abs(LinkList L, int n){
    int array[n+1];  // 輔助數(shù)組
    memset(array, 0,sizeof(array));  // 初始化數(shù)組
    LNode *p = L->next;
    LNode *pre = L;  // 作為p的前驅(qū)
    while(p != NULL){
        int num = abs(p->data);
        if(array[num] == 0)
            array[num]= 1;
        else{  // 如果之前出現(xiàn)過，則刪除該結(jié)點(diǎn)
            pre->next = p->next;
            LNode *q = p;
            free(q);
        }
        p = p->next;  // 移動指針
        pre = pre->next;
    }
}
  1. 有兩個(gè)循環(huán)單鏈表，編寫函數(shù)使得h2鏈接到h1之后，要求鏈接后的鏈表仍保持循環(huán)鏈表形式
typedef struct CNode{
    int data;
    CNode* next;
}CNode, *CList;

CList Joint(CList C1, CList C2){
    CNode *p = C1;  // 指向C1，C2的尾指針
    CNode *q = C2;
    while(p->next != C1){
        p = p->next;
    }
    
    while(q->next != C2){
        q = q->next;
    }
    p->next = C2;  //連接
    q->next = C1;  // 循環(huán)
    return C1;
}
  1. 判斷序列B是否是序列A的字序列
    設(shè)置兩個(gè)工作指針p，q，用pre記錄每次A中開始比較的結(jié)點(diǎn)，如果數(shù)據(jù)相等，向后移動指針，如果數(shù)據(jù)不相等，pre后移，即從一個(gè)新的結(jié)點(diǎn)開始匹配，q返回到B的第一個(gè)結(jié)點(diǎn)，這里默認(rèn)鏈表不帶頭結(jié)點(diǎn)。
int IsSub(LinkList &A, LinkList &B){
    LNode *p = A;
    LNode *pre = p;  // 記錄每次開始比較的結(jié)點(diǎn)
    LNode *q = B;
    while(p && q){
        if(p->data == q->data){
            p = p->next;
            q = q->next;
        }
        else{
            pre = pre->next;  // 沒有匹配成功，從一個(gè)新的結(jié)點(diǎn)開始比較
            p = pre;
            q = B;
        }
    }
    if(q == NULL)  // 代表B已經(jīng)匹配完
        return 1;
    else
        return 0;
}
  1. 刪掉有序鏈表中的相同元素
void Del_dup(LinkList &L){
    LNode *pre = L->next;
    if(pre == NULL)
        return;
    LNode *p = pre->next;
    while(p != NULL){
        if(pre->data == p->data){
            LNode *q = p;
            p = p->next;
            pre->next = p;
            free(q);
        }
        else{
//   這部分一定要放到else當(dāng)中，刪掉相同結(jié)點(diǎn)的話 pre不變，p后移
            pre = pre->next;
            p = p->next;
        }
    }
}
  1. 設(shè)C=\{a_1,b_1,a_2,b_2......a_n,b_n\}為線性表，將其拆分為兩個(gè)鏈表，其中C1=\{a_1,a_2,......a_n \} ，C2=\{a_1,b_1,a_2,b_2......a_n,b_n\}。
    不知道為什么閉括號顯示不出來，見鬼了！
    這里A用尾插法，B用頭插法即可。注意這里一定要用引用傳值，否則會報(bào)錯(cuò)。
LinkList Segment(LinkList C, LinkList& A, LinkList& B){
    LNode* hc = C->next;
    A =(LNode*)malloc(sizeof(LNode));  // A的表頭
    B =(LNode*)malloc(sizeof(LNode));  // B的表頭
    A->next = NULL;
    B->next = NULL;
    LNode* ra = A;
    int i = 0;
    while(hc != NULL){
        if(i % 2 == 0){
            LNode* new_node = (LNode*)malloc(sizeof(LNode));
            new_node->data = hc->data;
            new_node->next = NULL;
            ra->next = new_node;
            ra = new_node;
        }
        else{
            LNode* new_node = (LNode*)malloc(sizeof(LNode));
            new_node->data = hc->data;
            LNode *p = B->next;
            B->next = new_node;
            new_node->next = p;
        }
        i++;
        hc = hc->next;
    }
    ra->next = NULL;
    return B;
}
  1. 兩個(gè)遞增的鏈表，將其合并為一個(gè)遞減的鏈表，用原來兩個(gè)鏈表的空間存放合并后的鏈表。
void Merge_Sort(LinkList& A, LinkList& B){  // 把A和B和在一起 放在A當(dāng)中 用頭插法
    LNode *r, *p = A->next;
    LNode *q = B->next;
    A->next = NULL;
    while(p&& q){
        if(p->data <= q->data){
            r = p->next;
            p->next = A->next;
            A->next = p;
            p = r;
        }
        else{
            r = q->next;
            q->next = A->next;
            A->next = q;
            q = r;
        }
    }
        // 還有一個(gè)鏈表有剩余元素
    if(p)
        q = p;
    while(q){
        r = q->next;
        q->next = A->next;
        A->next = q;
        q = r;
    }
    
    free(B);
}
  1. 判斷循環(huán)雙鏈表是否對稱
// 循環(huán)雙鏈表
typedef struct DNode{
    int data;
    DNode* prior;
    DNode* next;
}DNode, *DLinkList;

bool IsSymmetry(DLinkList L){
    DNode *p = L->next;  // 頭節(jié)點(diǎn)
    DNode *q = L->prior;  // 尾結(jié)點(diǎn)
    while(p != q && p->next != q){
        if(p->data != q->data)
            return false;
        p = p->next;
        q = q->prior;
    }
    return true;
}
  1. 判斷鏈表是否有環(huán)，并返回環(huán)的入口
LNode* FindLoopStart(LNode *head){
    LNode *fast = head, *slow = head;
    while(slow != NULL && fast != NULL){
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
            break;
    }
    if(slow == NULL || fast->next == NULL)
        return NULL;
    LNode *p1 = head;  // 表頭
    LNode *p2 = slow;  // 相遇點(diǎn)
    while(p1 != p2){
        p1 = p1->next;
        p2 = p2->next;
    }
    return p1;
}
  1. 找到一個(gè)鏈表的中點(diǎn)
    利用雙指針，一個(gè)快一個(gè)慢，當(dāng)快指針到了尾部的時(shí)候，滿指針剛好到中間。以下代碼中，mid其實(shí)到了((high+low)/2)向上取整的位置
ListNode* findMid(ListNode* head){
    ListNode* slow = head;
    ListNode* fast = head;
    while(fast->next != NULL && fast->next->next != NULL){
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
  1. 鏈表歸并排序
ListNode* sortList(ListNode* head) {
    return sortList(head, NULL);
}

ListNode* Merge(ListNode* l1, ListNode* l2){
    ListNode* l = new ListNode(0);
    ListNode* p = l1;
    ListNode* q = l2;
    ListNode* node = l;
    while(p != NULL && q != NULL){
        if(p->val < q->val){
            node->next = p;
            p = p->next;
        }
        else{
            node->next = q;
            q = q->next;
        }
        node = node->next;
    }
    if(p != NULL){
        node->next = p;
       
    }
    if(q != NULL){
        node->next = q;
    }
    return l->next;
}
ListNode* sortList(ListNode* head, ListNode* tail) {
    if(head == NULL)
    return NULL;
    if(head->next == tail){  // 前面已經(jīng)排過序了 遞歸返回的時(shí)候 兩邊都帶有mid
        head->next = NULL;
        return head;
    }
    ListNode* slow=head, *fast=head;
    // 設(shè)置快慢指針 找到中點(diǎn)的位置
    while(fast != tail){  // 不能用NULL來當(dāng)判斷條件 因?yàn)楹竺婵赡苓€有節(jié)點(diǎn)
        slow = slow->next;
        fast = fast->next;
        if(fast != tail)
        fast = fast->next;
    }
    ListNode* mid = slow;  // mid其實(shí)到了((high+low)/2)向上取整的位置
    return Merge(sortList(head, mid),sortList(mid, tail));
}

總結(jié)

  1. 如果要求將新生成的鏈表存放在原來的鏈表當(dāng)中，比如對A和B進(jìn)行某種處理，將最終結(jié)果放在A中，一般的處理方法如下：（如第7題）
  • 記錄A->next = p，然后用p作為工作指針去遍歷A中的所有元素
  • 將A置空，如果有元素符合題目要求，將這個(gè)元素用尾插法插入A表
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容