[数据结构与算法] 链表题目集合

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 链表题目集合 -> 正文阅读

[数据结构与算法]链表题目集合

链表题总结

删除链表中等于给定值 val 的所有节点。

链接
思路:定义两个链表的指针cur,prev,prev指向cur的前一个,如果删除符合条件,则删除(prev->next = cur->next, free(cur), cur = cur->next).

typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val){
        //链表为空
        if (!head)
        {
            return NULL;
        }


        ListNode * cur = head;
        ListNode * prev = NULL;
        while (cur)
        {
            if (cur->val == val)
            {
                //删除
                //第一个结点
                if (head == cur)
                {
                    head = cur->next;
                    free(cur);
                    cur = head;
                }
                else
                {
                    //非第一个结点
                    prev->next = cur->next;
                    free(cur);
                    cur = prev->next;
                }
            }
            else
            {
                prev = cur;
                cur = cur->next;
            }
        }
        return head;
}

反转一个单链表。

链接
分析:
next = cur->next
cur->next = prev
prev = cur
cur = next

循环第一次
在这里插入图片描述
cur = head, prev = NULL, next = NULL

next = cur->next, cur->next = prev

prev = cur

cur = next

循环第二次

在这里插入图片描述
…同理

typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head){
    if (!head) //为空
    {
        return NULL;
    }

    ListNode * prev = NULL; //前一个
    ListNode * cur = head;
    ListNode * next = NULL; //后一个
    while (cur)
    {
        next = cur->next;
        cur->next = prev;

        prev = cur;
        cur = next;
    }

    return prev;
}

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个
中间结点。

链接
分析:定义两个指针分别为fast,slow,fast每次走2步,slow每次走1步,当fast为NULL,返回slow

typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head){
    ListNode * fast = head; 
    ListNode * slow = head;

    while (fast && fast->next) //注意判断顺序
    {
        fast = fast->next->next; //走2步
        slow = slow->next;       //走1步
    }
    return slow;
}

输入一个链表，输出该链表中倒数第k个结点

链接
分析:定义2个指针fast,slow都指向head, fast先走k步(注意链表长度<k的情况), 然后fast和slow各走一步至fast为NULL,返回slow.

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if (!pListHead || k <= 0)
        {
            return NULL;
        }
        ListNode * fast = pListHead;
        ListNode * slow = pListHead;
        
        //让快的先走k步
        while (k--)
        {
            if (NULL == fast) //链表长度<k
            {
                return NULL;
            }
            fast = fast->next;
        }
        //让快的和慢的每次走1步, 直至快的为NULL
        while (fast)
        {
            fast = fast->next;
            slow = slow->next;
        }
        //返回slow
        return slow;
    }
};

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成
的。

链接

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    //l1为空 返回l2
    if (!l1)
    {
        return l2;
    }
    //l2为空 返回l1
    if (!l2)
    {
        return l1;
    }
    ListNode * p1 = l1;
    ListNode * p2 = l2;
    ListNode p; //头节点
    ListNode * cur = &p;
    
    while (p1 && p2)
    {
        //l1 <= l2
        if (p1->val <= p2->val)
        {
            cur->next = p1;
            p1 = p1->next;
        }
        //l1 > l2
        else
        {
            cur->next = p2;
            p2 = p2->next;
        }
        cur = cur->next;
    }
    //判断l1是否为空
    if (p1)
    {
        cur->next = p1;
    }
    //判断l2是否为空
    if (p2)
    {
        cur->next = p2;
    }
    return p.next;
}

编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前。

链接
分析:用2个链表p1,p2分别连接把<x和>=连接起来,然后用p1把p2连接起来.


class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code herewf
        if (!pHead)
        {
            return NULL;
        }
        //头结点
        ListNode p1(0);
        ListNode p2(0);
        ListNode * cur = pHead;
        ListNode * pList1 = &p1;
        ListNode * pList2 = &p2;
        while (cur)
        {
            //<x的值链表
            if (cur->val < x)
            {
                pList1->next = cur;
                pList1 = pList1->next;
            }
            //>=x的值链表
            else
            {
                pList2->next = cur;
                pList2 = pList2->next;
            }
            cur = cur->next;
        }
        //合并链表
        pList2->next = NULL; //>x的链表后边置为NULL
        pList1->next = p2.next;
        return p1.next;

    }
};

链表的回文结构。

链接
分析:先返回中间结点,然后把链表分为前半段和后半段,把后半段逆置后与前半段比较,判断是否相等,最后(恢复链表)把后半段再次逆置,把前半段与后半段连接起来即可

class PalindromeList {
public:
    //链表逆置
    ListNode * reverseList(ListNode * A)
    {
        ListNode * cur = A;
        ListNode * prev = NULL;
        ListNode * next = NULL;
        while (cur)
        {
            next = cur->next;
            cur->next = prev;
            
            prev = cur;
            cur = next;
        }
        return prev;
    }
    //返回中间结点
    ListNode * backMiddle(ListNode * A)
    {
        ListNode * cur = A;
        ListNode * fast = A;
        ListNode * slow = A;
        ListNode * prev = NULL;
        int size = 0;
        //计数
        while (cur)
        {
            size++;
            cur = cur->next;
        }
        while (fast && fast->next)
        {
            prev = slow;
            fast = fast->next->next;
            slow = slow->next;
        }
        //偶数:slow  奇数:prev
        return size%2 ? slow : prev;
        
    }
    bool chkPalindrome(ListNode* A) {
        // write code here
        //链表为空或只有一个结点
        if (!A && !(A->next))
        {
            return false;
        }
        
        ListNode * mid = backMiddle(A); //中间结点
        ListNode * p1 = A;         //前一半
        ListNode * p2 = mid->next; //后一半
        mid->next = NULL;          //断开
        
        p2 = reverseList(p2); //逆置
        ListNode * pCur1 = p1;
        ListNode * pCur2 = p2;
        bool flag = true;
        while (pCur2)
        {
            if (pCur2->val != pCur1->val) //不是回文
            {
                flag = false;
                break;
            }
            pCur1 = pCur1->next;
            pCur2 = pCur2->next;
        }
        //还原
        reverseList(p2); 
        mid->next = p2;
        
        return flag;
    }
//     bool chkPalindrome(ListNode* A) {
//         // write code here
//            if (!A || !(A->next))
//                return true;
//         int arr[900] = {0};
//         ListNode * cur = A;
//         int i = 0;
//         while (cur)
//         {
//             arr[i++] = cur->val;
//             cur = cur->next;
//         }
//         int l = 0;
//         int r = i - 1;
//         while (l < r)
//         {
//             if (arr[l] != arr[r])
//             {
//                 return false;
//             }
//             l++;
//             r--;
//         }
//         return true;
//     }
};

输入两个链表，找出它们的第一个公共结点。

链接
分析:分别求headA和headB的长度,然后让长的先走k(长度差值),然后各走一步,相等就找到了公共结点.

typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    
    //分别求两个链表的长度
    ListNode * head1 = headA;
    ListNode * head2 = headB;
    int lenA = 0, lenB = 0;

    while (head1)
    {
        lenA++;
        head1 = head1->next;
    }
    while (head2)
    {
        lenB++;
        head2 = head2->next;
    }
    head1 = headA;
    head2 = headB;
    if (lenA > lenB) //A长
    {
        int size = lenA - lenB;
        while (size--)
        {
            head1 = head1->next;
        }
        while (head1)
        {
            if (head1 == head2)
            {
                return head1;
            }
            head1 = head1->next;
            head2 = head2->next;
        }

    }
    else             //B长
    {
        int size = lenB - lenA;
        while (size--)
        {
            head2 = head2->next;
        }
        while (head2)
        {
            if (head1 == head2)
            {
                return head1;
            }
            head1 = head1->next;
            head2 = head2->next;
        }
    }
    return NULL;
}

给定一个链表，判断链表中是否有环。

链接

typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {
    // 为空或只有一个结点
    if (!head || (head->next))
    {
        return false;
    }

    bool flag = false;
    ListNode * fast = head;
    ListNode * slow = head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow) //有环
        {
            flag = true;
            break;
        }
    }
    return flag;
}

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 NULL

链接
分析:fast(走2步)和slow(1步)找到相交的结点,然后让指向头的结点和相交的结点各走一步至相等,即为环的入口.

typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {
    if (!head || !(head->next))
    {
        return NULL;
    }
    ListNode * fast = head;
    ListNode * slow = head;
    bool flag = false;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow) //相遇点
        {
            flag = true;
            break;
        }
    }
    //有环
    ListNode * cur = head;
    if (flag) 
    {
        while (slow != cur) //环入口
        {
            slow = slow->next;
            cur = cur->next;
        }
    }
    else{
        return NULL;
    }
    return cur;
}