首页 > 代码库 > 链表学习笔记

链表学习笔记

2024-08-10 23:59:34   215人阅读

单向链表

struct ListNode {// 单向链表
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

从尾到头打印链表

vector<int> TravelListFromTailToHead(struct ListNode* head) {// 【从尾到头打印链表】
    vector<int> result;
    if(NULL == head)
        return result;
    ListNode *p = head;
    stack<ListNode*> nodeStack;
    while(p != NULL) {
        nodeStack.push(p);
        p = p->next;
    }
    while(!nodeStack.empty()) {
        p = nodeStack.top();
        result.push_back(p->val);
        nodeStack.pop();
    }
    return result;
}

链表中倒数第 k 个结点

ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {// 【链表中倒数第 k 个结点】
    if(NULL == pListHead || 0 == k) return NULL;
    ListNode *p1 = pListHead, *p2 = pListHead;// 使用快慢指针
    while(p2->next && k-- > 1) {// k-- > 1 一定要放在后面
        p2 = p2->next;
    }
    if(k > 1) return NULL;// 说明 k 值比节点数还大
    while(p2->next) {
        p2 = p2->next;
        p1 = p1->next;
    }
    return p1;
}

反转链表

ListNode* ReverseList(ListNode* pHead) {// 【反转链表】
    if(NULL == pHead) return NULL;
    ListNode *p = pHead, *pNext = pHead->next, *pPre = NULL;// 需要定义三个指针
    while(pNext) {
        p->next = pPre;
        pPre = p;
        p = pNext;
        pNext = pNext->next;
    }
    p->next = pPre;
    return p;
}

合并两个排序的链表

ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {// 【合并两个排序的链表】
    if(NULL == pHead1) return pHead2;
    if(NULL == pHead2) return pHead1;
    ListNode *pHead = NULL, *p;// pHead：保存新链表表头；p：用于新链表遍历生成
    if(pHead1->val <= pHead2->val) {
        pHead = pHead1;
        pHead1 = pHead1->next;
    } else {
        pHead = pHead2;
        pHead2 = pHead2->next;
    }
    p = pHead;
    while(pHead1 && pHead2) {
        if(pHead1->val <= pHead2->val) {
            p->next = pHead1;
            pHead1 = pHead1->next;
        } else {
            p->next = pHead2;
            pHead2 = pHead2->next;
        }
        p = p->next;
    }
    while(pHead1) {
        p->next = pHead1;
        p = p->next;
        pHead1 = pHead1->next;
    }
    while(pHead2) {
        p->next = pHead2;
        p = p->next;
        pHead2 = pHead2->next;
    }
    return pHead;
}

两个链表的第一个公共结点

ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2) {// 【两个链表的第一个公共结点】
    ListNode *p = pHead1, *q = pHead2;
    // 先计算两个链表的长度
    unsigned int nLength1 = 0, nLength2 = 0;
    while(p != NULL && q != NULL) {
        nLength1++;
        nLength2++;
        p = p->next;
        q = q->next;
    }
    while(p != NULL) {
        nLength1++;
        p = p->next;
    }
    while(q != NULL) {
        nLength2++;
        q = q->next;
    }
    // 根据两链表的长度差，长的链表先走这个差值的步数
    int n = abs(nLength1 - nLength2);
    p = pHead1;
    q = pHead2;
    if(nLength1 < nLength2) {
        p = pHead2;
        q = pHead1;
    }
    while(n--)
        p = p->next;
    // 对齐后，一起走，直到遇到第一个公共节点
    while(p != NULL && q != NULL && p != q) {
        p = p->next;
        q = q->next;
    }
    return p;
}

链表中环的入口结点

ListNode* getMeetNode(ListNode* pHead) {// 用快慢指针，必然相会于环内某个节点，返回这个节点，否则返回 NULL
    if(NULL == pHead) return NULL;
    ListNode* pSlow = pHead->next;
    if(NULL == pSlow) return NULL;
    ListNode* pFast = pSlow->next;
    while(pSlow != NULL && pFast != NULL) {
        if(pFast == pSlow)
            return pFast;
        pFast = pFast->next;
        pSlow = pSlow->next;
        if(pFast != pSlow)
            pFast = pFast->next;
    }
    return NULL;
}
ListNode* EntryNodeOfLoop(ListNode* pHead) {// 【链表中环的入口结点】
    ListNode* meetNode = getMeetNode(pHead);// 用快慢指针得到环内某个节点
    if(NULL == meetNode)
        return NULL;
    int n = 1;
    //　用这个环内节点计算得到环内节点数
    ListNode* p = meetNode->next;
    while(p != meetNode) {
        p = p->next;
        ++n;
    }
    // 用两个指针，一个指针先走环内节点个数的步数，另一个节点在链表头
    // 当两个节点相遇时，此时的节点即是环的入口节点
    p = pHead;
    while(n--)
        p = p->next;
    ListNode* p1 = pHead;
    while(p1 != p) {
        p = p->next;
        p1 = p1->next;
    }
    return p;
}

判断链表是否是回文结构

bool IsPalindrome(ListNode* pHead) {// 【判断链表是否是回文结构】
    // 使用快慢指针，找到链表的中间
    ListNode* pFast = pHead;
    ListNode* pSlow = pHead;
    while(pFast != NULL && pSlow != NULL) {
        pFast = pFast->next;
        pSlow = pSlow->next;
        if(pFast != NULL)
            pFast = pFast->next;
    }

    pSlow = ReverseList(pSlow);// 从中间节点开始将链表反转（链表被改变，即现场改变）

    // 从两头开始往中间遍历，判断是否是回文结构
    bool flag = true;
    ListNode *p1 = pHead, *p2 = pSlow;
    while(p2 != NULL) {
        if(p1->val != p2->val) {
            flag = false;
        }
        p1 = p1->next;
        p2 = p2->next;
    }

    ReverseList(pSlow);// 将链表恢复（恢复现场）

    return flag;
}

删除链表中的重复结点

删除链表中相邻的重复结点（保留一个）

void DeleteDuplication(ListNode* &pHead) {// 【删除链表中相邻的重复结点（保留一个）】
    if(NULL == pHead) return;
    ListNode *p1 = pHead, *p2 = p1->next;
    while(p2 != NULL) {
        if(p2->val == p1->val) {
            while(p2 != NULL && p2->val == p1->val) {
                ListNode* p = p2;
                p2 = p2->next;
                delete p;
                p = NULL;
            }
            p1->next = p2;
        }
        if(NULL != p2)
            p2 = p2->next;
        p1 = p1->next;
    }
}

删除链表中重复结点（保留一个）

void DeleteDuplication2(ListNode* &pHead) {// 【删除链表中重复结点（保留一个）】
    if(NULL == pHead) return;
    set<int> s;
    s.insert(pHead->val);
    ListNode* p = pHead, *pNode = pHead->next;
    while(pNode != NULL) {
        if(s.find(pNode->val) == s.end()) {
            s.insert(pNode->val);
            p->next = pNode;
            p = p->next;
            pNode = pNode->next;
        } else {
            ListNode* q = pNode;
            pNode = q->next;
            delete q;
            q = NULL;
            p->next = NULL;
        }
    }
}

删除链表中相邻重复结点

void DeleteDuplication3(ListNode* &pHead) {// 【删除链表中相邻重复结点】
    if(NULL == pHead) return;
    ListNode *pPre = NULL, *pNode = pHead;
    while(pNode != NULL) {
        ListNode* pNext = pNode->next;
        if(pNext != NULL && pNext->val == pNode->val) {
            const int val = pNode->val;
            ListNode* p = pNode;
            while(p != NULL && val == p->val) {
                pNext = p->next;
                delete p;
                p = pNext;
            }
            if(NULL == pPre)
                pHead = pNext;
            else
                pPre->next = pNext;
            pNode = pNext;
        } else {
            pPre = pNode;
            pNode = pNode->next;
        }
    }
}

复杂链表

struct RandomListNode {// 复杂链表
    int val;
    struct RandomListNode *next, *random;
    RandomListNode(int x) : val(x), next(NULL), random(NULL) {}
};

复杂链表的复制

RandomListNode* Clone(RandomListNode* pHead) {// 【复杂链表的复制】
    if(NULL == pHead) return NULL;
    RandomListNode *p = pHead;
    while(p != NULL) {
        RandomListNode *pNode = new RandomListNode(p->val);
        pNode->next = p->next;
        p->next = pNode;
        p = pNode->next;
    }

    p = pHead;
    RandomListNode *pClone;
    while(p != NULL) {
        pClone = p->next;
        if(p->random != NULL)
            pClone->random = p->random->next;
        p = pClone->next;
    }

    p = pHead;
    RandomListNode *pCloneHead = pHead->next;
//    pClone = pHead->next;
//    p = pClone->next;
//    while(p != NULL) {
//        pClone->next = p->next;
//        pClone = pClone->next;
//        p->next = pClone->next;
//        p = p->next;
//    }
    RandomListNode *tmp;
    while(p->next) {
        tmp = p->next;
        p->next = tmp->next;
        p = tmp;
    }

    return pCloneHead;
}


链表学习笔记


联系
我们