数据结构：力扣OJ题

素颜马尾好姑娘i 2023-10-14 18:34 15阅读 0赞

## ![5ef9902dcba44da08469f1effdd62978.png][] ##

**目录**

编辑题一：链表分割

思路一：

题二：相交链表

思路一：

题三：环形链表

思路一：

题四：链表的回文结构

思路一：

链表反转：

查找中间节点：

本人实力有限可能对一些地方解释的不够清晰，可以自己尝试读代码，望海涵！

--------------------

## 题一：链表分割 ##

现有一链表的头指针 ListNode\* **pHead**，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

### 思路一： ###

1.分别创建一个记录**小于x的“小”结构体**，和记录**大于等于x的“大”结构体**，

2.然后**malloc函数动态开辟**一个结构体大小的空间，这时**head和tail都指向同一位置**，将phead->val与x比较，小于想，放入less中，大于等于x放入great中，

**3.当phead为NULL时**，将两个“大”“小”结构体链接起来，记录lesshead节点，然后**free释放开辟的动态内存空间，返回记录lesshead的地址。**

![ea449792818440a5818e6759ec50000a.png][]

ListNode* partition(ListNode* phead, int x) 
        {
            
            struct ListNode* head = phead ; 
            struct ListNode* lesshead ;
            struct ListNode* greathead ; 
            struct ListNode* lesstail ; 
            struct ListNode* greattail ; 
            //动态开辟空间
            lesshead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode));
            greathead = greattail = (struct ListNode*)malloc(sizeof(struct ListNode));
    
            while(head)
            {
                //小于x的尾插到lessTail
                if(head->val < x)
                {
                    lesstail->next  = head;
                    lesstail = lesstail->next;            
                }
                //大于等于x的尾插到greaterTail
                else
                {
                    greattail->next  = head;
                    greattail = greattail->next; 
                }
                //下一个位置
                head = head->next;  
            }
            //小的接上大的
            lesstail->next = greathead->next;
            greattail->next = NULL;
    
            //新头节点
            struct ListNode* Phead = lesshead->next;
            //销毁
            free(lesshead);
            free(greathead);
            
    
            return Phead;
        }

## 题二：相交链表 ##

给你两个单链表的头节点 `headA` 和 `headB` ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 `null` 。

图示两个链表在节点 `c1` 开始相交**：**

[![428310f8cfd5c1b1c308b43ddc15b510.png][]][428310f8cfd5c1b1c308b43ddc15b510.png 1]

题目数据 **保证** 整个链式结构中不存在环。

**注意**，函数返回结果后，链表必须 **保持其原始结构** 。

### 思路一： ###

1.先分别将A和B遍历一遍，**计算出长度len**  
2.计算**长度差Slen**，让长的先指向Slen个next位置  
3.此时再同时遍历，直到**A和B的地址相同**，  
4.返回的就是第一个交点

![922f5910c7934996baa0177a84d7366d.png][]

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
    {
        struct ListNode* curA = headA,*curB = headB;
        int len1 = 1,len2 = 1; 
        //计算链表长度
        while(curA)
        {
            curA = curA->next;
            len1++;
        }
        while(curB)
        {
            curB = curB->next;
            len2++;
        }
        //如果此时遍历结束地址不相等，说明没有相交点
        if(curA != curB)
        {
            return NULL;
        }
        //abs是计算差值绝对值函数
        int Slen = abs(len1 - len2);
        //二次遍历的长短链表
        struct ListNode* longlist = headA,*shortlist = headB;
        if(len1 <  len2)
        {
            longlist = headB;
            shortlist = headA;
        }
        //让longlist和shortlist的长度相同
        while(Slen--)
        {
            longlist = longlist->next;
        }
        //找到第一个交点
        while(longlist != shortlist)
        {
            longlist = longlist->next;
            shortlist = shortlist->next;
        }
        //输出交点地址
        return longlist;
    }

## 题三：环形链表 ##

给你一个链表的头节点 `head` ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 `next` 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 `pos` 来表示链表尾连接到链表中的位置（索引从 0 开始）。**注意：`pos` 不作为参数进行传递** 。仅仅是为了标识链表的实际情况。

*如果链表中存在环* ，则返回 `true` 。 否则，返回 `false` 。

**示例 1：**

![6f451eadf3b4cbe31fa7d55c274bdf94.png][]

### 思路一： ###

**快慢指针思路:**  
1.创建快慢指针fast和slow；  
2.开始位置相同，slow每次指向下一个地址， fast每次指向下下个地址；  
3.循环判断，直到**slow=fast地址相同**；

4，相同则说明链表**存在环**；  
反之，fast或fast->next尾NULL则**不存在环**。

![81e319a9a3ab4892bcbb1e9e2f538256.png][]

bool hasCycle(struct ListNode *head)
    {
        struct ListNode* slow = head;
        struct ListNode* fast = head;
        //fast或fast->next尾NULL则不存在环
        while(fast && fast->next)
        {
            //slow每次指向下一个地址， fast每次指向下下个地址
            slow = slow->next;
            fast = fast->next->next;
            //相同则说明链表存在环
            if(slow == fast)
            {
                return true;
            }
        }
        
        return false;
    }

## 题四：链表的回文结构 ##

### 思路一： ###

如下：两种方法，得到的节点去循环判断，如果newnode或者head一个为NULL，则说明是回文结构，如果在循环中结束·，则不是回文结构。

#### 链表反转： ####

三个变量n1=NULL,n2=head,n3,如果n2**不为NULL**，则n3=n2->next，循环如果n2为NULL，就停下来，**当n3为空时n3就不进行变化**，最后n1会停在最后一个位置，这个时候逆置完成。

![bacfbd14f7fb4a35ac9ac08be007b05b.png][]

#### 查找中间节点： ####

分别定义**快慢两个指针**，快指针一次**前进两个地址**，慢指针一次**前进一个地址**，当**奇数时**快指针的**next为NULL时**，当链表为**偶数时判断条件为地址为NULL**，停下来，此时**慢指针就在链表中间节点**上。

![c0ddb6c958644684beaf72949f5161b5.png][]

//将链表反转
    struct ListNode* reverseList(struct ListNode* head)
    {
      struct ListNode* n1,*n2,*n3;
      n1 = NULL;
      n2 = head;
      if(n2)
      n3 = n2->next;
    
      while(n2)
      {
          n2->next = n1;
          n1 = n2;
          n2 = n3;
        if(n3)
          n3 = n3->next;
      }
      return n1;
    }
    //得到链表中间节点
    struct ListNode* middleNode(struct ListNode* head)
    {
        struct ListNode* slow = head;
        struct ListNode* fast = head;
        while(fast && fast->next)
        {
            
            slow = slow->next;
            fast = fast->next->next;
    
        }
        return slow;
    }
    class PalindromeList {
    public:
        bool chkPalindrome(ListNode* head) 
        {
            struct ListNode* mid = middleNode(head);
            struct ListNode* newnode = reverseList(mid);
            //一个为空自己退出
            while(newnode && head)
            {
                //不相同，则不是回文结构
                if(newnode->val != head->val)
                {
                    return false;
                }
    
                newnode = newnode->next;
                head = head->next; 
            }
            return true;
        }
    };

## 本人实力有限可能对一些地方解释的不够清晰，可以自己尝试读代码，望海涵！ ##

[5ef9902dcba44da08469f1effdd62978.png]: https://img-blog.csdnimg.cn/5ef9902dcba44da08469f1effdd62978.png
[ea449792818440a5818e6759ec50000a.png]: https://img-blog.csdnimg.cn/ea449792818440a5818e6759ec50000a.png
[428310f8cfd5c1b1c308b43ddc15b510.png]: https://img-blog.csdnimg.cn/img_convert/428310f8cfd5c1b1c308b43ddc15b510.png
[428310f8cfd5c1b1c308b43ddc15b510.png 1]: https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/160_statement.png
[922f5910c7934996baa0177a84d7366d.png]: https://img-blog.csdnimg.cn/922f5910c7934996baa0177a84d7366d.png
[6f451eadf3b4cbe31fa7d55c274bdf94.png]: https://img-blog.csdnimg.cn/img_convert/6f451eadf3b4cbe31fa7d55c274bdf94.png
[81e319a9a3ab4892bcbb1e9e2f538256.png]: https://img-blog.csdnimg.cn/81e319a9a3ab4892bcbb1e9e2f538256.png
[bacfbd14f7fb4a35ac9ac08be007b05b.png]: https://img-blog.csdnimg.cn/bacfbd14f7fb4a35ac9ac08be007b05b.png
[c0ddb6c958644684beaf72949f5161b5.png]: https://img-blog.csdnimg.cn/c0ddb6c958644684beaf72949f5161b5.png