系列文章目錄

前言

一、左旋轉字串

左旋轉字串

1.題目描述

字串的左旋轉操作是把字串前面的若干個字符轉移到字串的尾部，請定義一個函式實作字串左旋轉操作的功能，比如，輸入字串"abcdefg"和數字2，該函式將回傳左旋轉兩位得到的結果"cdefgab"，

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;
}

二、回文鏈表

回文鏈表

1.題目描述

請判斷一個鏈表是否為回文鏈表，

2.解題思路

思路二的效率更高，所以實作思路二:

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;
}

三、兩個鏈表第一個公共節點

兩個鏈表第一個公共結點

1.題目描述

輸入兩個鏈表，找出它們的第一個公共節點，

2.解題思路

1. 計算兩個鏈表的長度
2. 計算兩個鏈表相差的長度
3. 長度更長的鏈表先走更長的相差長度，再一同走，第一次相遇則是公共節點
   
   代碼如下：

#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;
}

總結

以上就是今天要講的內容，本文僅僅簡單介紹了鏈表的使用和左旋字串，這些題目可能以后面試時會用到，我們務必掌握，另外，如果上述有任何問題，請懂哥指教，不過沒關系，主要是自己能堅持，更希望有一起學習的同學可以幫我指正，但是如果可以請溫柔一點跟我講，愛與和平是永遠的主題，愛各位了，