学会LeetCode三道题

拼搏现实的明天。 2023-01-14 04:54 123阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center]

# 系列文章目录 #

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

### 文章目录 ###

*  系列文章目录
 *  前言
 *  一、左旋转字符串
 *   *   *  1.题目描述
         *  2.解题思路
 *  二、回文链表
 *   *   *  1.题目描述
         *  2.解题思路
 *  三、两个链表第一个公共节点
 *   *   *  1.题目描述
         *  2.解题思路
 *  总结

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

# 前言 #

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

![在这里插入图片描述][20210420081826657.png]

# 一、左旋转字符串 #

[左旋转字符串][Link 1]

### 1.题目描述 ###

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。  
![在这里插入图片描述][20210420082133617.png]![在这里插入图片描述][20210420082154764.png]

### 2.解题思路 ###

方法1:定义临时变量，两个循环，此方法效率比较低。  
  
代码如下：

#include<string.h>
    char* reverseLeftWords(char* s, int n)
    { 
        int len=strlen(s);
        n=n%len;
        int i=0;
        int j=0;
        for(i=0;i<n;i++)  //旋转n个，
        { 
            char tmp=*s;        //定义一个临时变量
            for(j=0;j<len-1;j++)//旋转一个
            { 
                *(s+j)=*(s+j+1);
            }
            *(s+len-1)=tmp;
        }
        return s;
    }
    int main()
    { 
    	int k = 0;
    	char arr[] = "bit education";
    	int len = strlen(arr);
    	scanf("%d", &k);
    	left_move1(arr, k,len);
    	printf("%s\n", arr);
    	return 0;
    }

方法2:把字符串分为两个部分，一部分k前面的字符，一部分k后面的字符，先旋转前面字符，再旋转后面字符，再整体旋转。  
代码如下：

void reverse(char* left, char* right)       //方法2
    { 
    	assert(left&&right);
    	while (left < right)
    	{ 
    		char tmp = *left;
    		*left = *right;
    		*right = tmp;
    		left++;
    		right--;
    	}
    }
    char* left_move2(char* arr, int k)
    { 
    	assert(arr);
    	int len = strlen(arr);
    	reverse(arr, arr + k - 1);
    	reverse(arr + k, arr + len - 1);
    	reverse(arr, arr + len - 1);
    	return arr;
    }
    int main()
    { 
    	int k = 0;
    	char arr[] = "bit education";
    	int len = strlen(arr);
    	scanf("%d", &k);
    	left_move2(arr, k);
    	printf("%s\n", arr);
    	return 0;
    }

# 二、回文链表 #

[回文链表][Link 2]

### 1.题目描述 ###

请判断一个链表是否为回文链表。  
![在这里插入图片描述][20210420083712251.png]  
![在这里插入图片描述][202104200837223.png]

### 2.解题思路 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70]  
思路二的效率更高，所以实现思路二:

1.  先找到中间节点
2.  中间节点后半部分逆置
3.  比较前面和后面的节点  
    代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
    #include<stdio.h>
    #include<stdbool.h>
    struct ListNode
    { 
    	int val;
    	struct ListNode* next;
    };
    struct ListNode* middleNode(struct ListNode* head)
    { 
    	struct ListNode* fast = head, *slow = head;
    	while (fast&&fast->next)
    	{ 
    		fast = fast->next->next;
    		slow = slow->next;
    	}
    	return slow;
    }
    struct ListNode* reverse(struct ListNode* head)
    { 
    	struct ListNode* cur = head;
    	struct ListNode* newhead = NULL;
    	while (cur)
    	{ 
    		struct ListNode* next = cur->next;
    		cur->next = newhead;
    		newhead = cur;
    		cur = next;
    	}
    	return newhead;
    }
    bool isPalindrome(struct ListNode* head)
    { 
    	struct ListNode* mid = middleNode(head);
    	struct ListNode* rhead = reverse(mid);
    	while (head&&rhead)
    	{ 
    		if (head->val != rhead->val)
    		{ 
    			return false;
    		}
    		else
    		{ 
    			head = head->next;
    			rhead = rhead->next;
    		}
    	}
    	return true;
    }

# 三、两个链表第一个公共节点 #

[两个链表第一个公共结点][Link 3]

### 1.题目描述 ###

输入两个链表，找出它们的第一个公共节点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 4]

### 2.解题思路 ###

1.  计算两个链表的长度
2.  计算两个链表相差的长度
3.  长度更长的链表先走更长的相差长度，再一同走，第一次相遇则是公共节点  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 5]  
    代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
    #include<stdio.h>
    #include<math.h>
    struct ListNode
    { 
    	int val;
    	struct ListNode* next;
    };
    //1.求出两个链表的长度
    //2.比较两个链表谁更长
    //3.求出两个链表的相差的长度
    //4.长的链表先走相差的长度，然后两链表一起走完
    struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
    { 
    	if (headA == NULL || headB == NULL)
    	{ 
    		return NULL;
    	}
    	struct ListNode* curA = headA, *curB = headB;
    	int lenA = 0;
    	int lenB = 0;
    	while (curA->next)  //如果curA是空链表，则程序崩溃
    	{ 
    		lenA++;
    		curA = curA->next;
    	}
    	while (curB->next)
    	{ 
    		lenB++;
    		curB = curB->next;
    	}
    	if (curA != curB)
    	{ 
    		return NULL;
    	}
    	struct ListNode* longList = headA, *shortList = headB;
    	if (lenB > lenA)
    	{ 
    		longList = headB;
    		shortList = headA;
    	}
    	int gap = abs(lenA - lenB);
    	while (gap--)
    	{ 
    		longList = longList->next;
    	}
    	while (longList != shortList)
    	{ 
    		longList = longList->next;
    		shortList = shortList->next;
    	}
    	return longList;
    }
    int main()
    { 
    	return 0;
    }

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

# 总结 #

以上就是今天要讲的内容，本文仅仅简单介绍了链表的使用和左旋字符串，这些题目可能以后面试时会用到，我们务必掌握。另外，如果上述有任何问题，请懂哥指教，不过没关系，主要是自己能坚持，更希望有一起学习的同学可以帮我指正，但是如果可以请温柔一点跟我讲，爱与和平是永远的主题，爱各位了。  
![在这里插入图片描述][20210420090130639.png_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/26459acaad6c472395cf99183de66d0d.png
[20210420081826657.png]: /images/20221022/9af7d56da8844693842bbe6b4bd9410a.png
[Link 1]: https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/
[20210420082133617.png]: https://img-blog.csdnimg.cn/20210420082133617.png
[20210420082154764.png]: /images/20221022/b2674b7c5f8247f4ad45de2b5bb49368.png
[Link 2]: https://leetcode-cn.com/problems/palindrome-linked-list/
[20210420083712251.png]: /images/20221022/8bacef580992401da80bd6418fe7c547.png
[202104200837223.png]: /images/20221022/e77c31f0fae942edaa42cad855f67e21.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70]: /images/20221022/8c2d54820fa143e68cccfd48219b9841.png
[Link 3]: https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 1]: /images/20221022/85420618afbc40258afcb24e266aa12c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 2]: /images/20221022/a19ceaeef57a4152be2d1700c3b6efd1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 3]: /images/20221022/81b4f32b3aa8478f8ad3a86f389d24da.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 4]: /images/20221022/e8d58d2654234c9e856c5c705610051d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 5]: /images/20221022/0d2b365648824547a92bd54d85892ad7.png
[20210420090130639.png_pic_center]: /images/20221022/51f165c50ff3499fb68acc0bf0d3ce84.png