数据结构力扣OJ题

目录

编辑题一：链表分割

思路一：

题二：相交链表

思路一：

题三：环形链表

 思路一：

题四：链表的回文结构

思路一：

链表反转：

查找中间节点：

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

---

题一：链表分割

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

思路一：

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

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

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

1.  
   ListNode* partition(ListNode* phead, int x)
2.  
   {
3.  
    
4.  
   struct ListNode* head = phead ;
5.  
   struct ListNode* lesshead ;
6.  
   struct ListNode* greathead ;
7.  
   struct ListNode* lesstail ;
8.  
   struct ListNode* greattail ;
9.  
   //动态开辟空间
10.  
    lesshead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode));
11.  
    greathead = greattail = (struct ListNode*)malloc(sizeof(struct ListNode));
12.  
     
13.  
    while(head)
14.  
    {
15.  
    //小于x的尾插到lessTail
16.  
    if(head->val < x)
17.  
    {
18.  
    lesstail->next = head;
19.  
    lesstail = lesstail->next;
20.  
    }
21.  
    //大于等于x的尾插到greaterTail
22.  
    else
23.  
    {
24.  
    greattail->next = head;
25.  
    greattail = greattail->next;
26.  
    }
27.  
    //下一个位置
28.  
    head = head->next;
29.  
    }
30.  
    //小的接上大的
31.  
    lesstail->next = greathead->next;
32.  
    greattail->next = NULL;
33.  
     
34.  
    //新头节点
35.  
    struct ListNode* Phead = lesshead->next;
36.  
    //销毁
37.  
    free(lesshead);
38.  
    free(greathead);
39.  
     
40.  
     
41.  
    return Phead;
42.  
    }

题二：相交链表

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

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

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

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

思路一：

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

1.  
   struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
2.  
   {
3.  
   struct ListNode* curA = headA,*curB = headB;
4.  
   int len1 = 1,len2 = 1;
5.  
   //计算链表长度
6.  
   while(curA)
7.  
   {
8.  
   curA = curA->next;
9.  
   len1 ;
10.  
    }
11.  
    while(curB)
12.  
    {
13.  
    curB = curB->next;
14.  
    len2 ;
15.  
    }
16.  
    //如果此时遍历结束地址不相等，说明没有相交点
17.  
    if(curA != curB)
18.  
    {
19.  
    return NULL;
20.  
    }
21.  
    //abs是计算差值绝对值函数
22.  
    int Slen = abs(len1 - len2);
23.  
    //二次遍历的长短链表
24.  
    struct ListNode* longlist = headA,*shortlist = headB;
25.  
    if(len1 < len2)
26.  
    {
27.  
    longlist = headB;
28.  
    shortlist = headA;
29.  
    }
30.  
    //让longlist和shortlist的长度相同
31.  
    while(Slen--)
32.  
    {
33.  
    longlist = longlist->next;
34.  
    }
35.  
    //找到第一个交点
36.  
    while(longlist != shortlist)
37.  
    {
38.  
    longlist = longlist->next;
39.  
    shortlist = shortlist->next;
40.  
    }
41.  
    //输出交点地址
42.  
    return longlist;
43.  
    }

题三：环形链表

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

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

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

示例 1：

 思路一：

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

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

1.  
   bool hasCycle(struct ListNode *head)
2.  
   {
3.  
   struct ListNode* slow = head;
4.  
   struct ListNode* fast = head;
5.  
   //fast或fast->next尾NULL则不存在环
6.  
   while(fast && fast->next)
7.  
   {
8.  
   //slow每次指向下一个地址， fast每次指向下下个地址
9.  
   slow = slow->next;
10.  
    fast = fast->next->next;
11.  
    //相同则说明链表存在环
12.  
    if(slow == fast)
13.  
    {
14.  
    return true;
15.  
    }
16.  
    }
17.  
     
18.  
    return false;
19.  
    }

题四：链表的回文结构

思路一：

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

链表反转：

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

查找中间节点：

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

1.  
   //将链表反转
2.  
   struct ListNode* reverseList(struct ListNode* head)
3.  
   {
4.  
   struct ListNode* n1,*n2,*n3;
5.  
   n1 = NULL;
6.  
   n2 = head;
7.  
   if(n2)
8.  
   n3 = n2->next;
9.  
    
10.  
    while(n2)
11.  
    {
12.  
    n2->next = n1;
13.  
    n1 = n2;
14.  
    n2 = n3;
15.  
    if(n3)
16.  
    n3 = n3->next;
17.  
    }
18.  
    return n1;
19.  
    }
20.  
    //得到链表中间节点
21.  
    struct ListNode* middleNode(struct ListNode* head)
22.  
    {
23.  
    struct ListNode* slow = head;
24.  
    struct ListNode* fast = head;
25.  
    while(fast && fast->next)
26.  
    {
27.  
     
28.  
    slow = slow->next;
29.  
    fast = fast->next->next;
30.  
     
31.  
    }
32.  
    return slow;
33.  
    }
34.  
    class PalindromeList {
35.  
    public:
36.  
    bool chkPalindrome(ListNode* head)
37.  
    {
38.  
    struct ListNode* mid = middleNode(head);
39.  
    struct ListNode* newnode = reverseList(mid);
40.  
    //一个为空自己退出
41.  
    while(newnode && head)
42.  
    {
43.  
    //不相同，则不是回文结构
44.  
    if(newnode->val != head->val)
45.  
    {
46.  
    return false;
47.  
    }
48.  
     
49.  
    newnode = newnode->next;
50.  
    head = head->next;
51.  
    }
52.  
    return true;
53.  
    }
54.  
    };

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

这篇好文章是转载于：学新通技术网