当前位置：首页 > article >正文

【C语言】数据结构|链表|入门|leetcode

article 2025/1/9 15:30:38

主页：114514的代码大冒

（欢迎小伙伴呀hi✿(。◕ᴗ◕。)✿ ）

Gitee：庄嘉豪 (zhuang-jiahaoxxx) - Gitee.com

文章目录

前言

祝你武运昌隆

一、相交链表

描述：

示例：

思路一：
A，B两个链表的长度可能相等，也可能不相等，

如果相等，我们设置两个指针分别从A，B链表的表头开始遍历，逐个节点进行比较，如果在某个节点时，两个指针指向的地址一致且不为空，则说明发生相交

如果两个链表的长度不一致，那么我们计算出两个链表各自的长度后，比较出较长的链表，并使指向该链表的指针向前走n个节点（这个数值为两个链表的长度差）

如图：

注意：
这里是不能存在两个链表交叉的可能性的

就是如下图这种情况：

代码：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
        struct ListNode* curA = headA;
        struct ListNode *curB = headB;

        if(curA == NULL)
        {
            return NULL;
        }
        if(curB == NULL)
        {
            return NULL;
        }
        int num1 = 0;
        int num2 = 0;

        while (curA)
        {
            num1++;
            curA = curA->next;

        }
        curA = headA;
        while (curB)
        {
            num2++;
            curB = curB->next;
        }
        curB = headB;

        int n = abs(num1-num2);
        if(num1 > num2)
        {
            while(n--)
            {
                curA = curA->next;
            }
        }
        else
        {
            while(n--)
            {
                curB =curB->next;
            }
        }


        while(curA && curB)
        {
            if((curA == curB)&&(curA !=NULL))
            {
                return curA;
            }
            curA = curA->next;
            curB = curB->next;
        }

        return NULL;
    
}

思路二:
任然设置两个指针，分别指向两个链表的头结点，然后开始遍历，当其中一个指针走到了链表的

空节点，则从另一个链表的表头接着进行逐节点遍历，另一个指针也是如法炮制，更重要的是，在这个过程中要相互比较，一旦相等便返回该节点

如图：

这里还遗留了两个链表不想交的情况，我们利用如上图所示的办法依然能够完成我们想要的效果

代码：

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *A = headA, *B = headB;
        while (A != B) {
            A = A != nullptr ? A->next : headB;
            B = B != nullptr ? B->next : headA;
        }
        return A;
    }
};

二、旋转链表

描述：

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

示例：

思路：

这就相当于旋转字符串中的右旋，通过观察我们可以发现右旋n个节点就是将尾部的n个节点移动到前端

代码:

struct ListNode* rotateRight(struct ListNode* head, int k){
        struct ListNode* hd  = head;
        struct ListNode* cur = head;
        struct ListNode* prev = head;

        struct ListNode* fast = head;
        struct ListNode* slow = head;
        struct ListNode* p = NULL;
        if(hd == NULL)
        {
            return NULL;
        }
        if(hd->next == NULL)
        {
            return hd;
        }

        int n  = 0; 
        while(cur)
        {
            n++;
            if(cur->next == NULL)
            {
                p = cur;
            }
            cur = cur->next;
        }
         k = k % n;
        if( k == 0)
        {
            return hd;
        }
        while(k--)
        {
            fast = fast->next;
        }
        while(fast)
        {
            if(fast->next == NULL)
            {
                prev = slow;
            }

            fast = fast->next;
            slow = slow->next;

        }
        p->next = hd;
        prev->next = NULL;

        return slow;


}

三，回文链表

描述：

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例一：

输入：head = [1,2,2,1]
输出：true

示例二：

思路：

将链表均分成前后两段（奇数个节点时，忽略中间节点），然后逆置后半段链表，然后设置两个指针从前后分别同步开始遍历

代码：

bool isPalindrome(struct ListNode* head){
    struct ListNode* cur = head;
    struct ListNode* newcur = head;

    struct ListNode* prev = head;
    struct ListNode* next = head;
    int count = 0;
    int i = 1;
    if(head == NULL)
        return false;
    if(head->next == NULL)
        return true;


    while(cur)
    {
        count++;
        cur = cur->next;
    }
    cur = head;
    while(i< (count/2 + 1))
    {
        i++;
        cur = cur->next;

    }
    prev = cur;
    next = cur->next;
    while(cur)
    {
        cur->next = prev;
        prev = cur;
        cur = next;
        if(cur != NULL)
            next = cur->next;
    }
    i = 0;
    newcur = prev;
    cur = head;
    while(i<count/2)
    {
        i++;
        if(newcur->val != cur->val)
        {
            return false;
        }
        newcur = newcur->next;
        cur = cur->next;
    }
    return true;

}