# OJ question

First, let's understand the forms of OJ questions. There are two forms:

• Interface type

Provide an interface function instead of a complete program. Just implement this function. After submitting the program, this code will be submitted to the OJ server, and it will be merged with other test programs (header file and main function)

Test cases generally interact through parameters and return values.

• IO type

Write the code area without giving you anything. Write your own complete program, header file, main function, algorithm logic

We need to input test cases for interface IO and output the structure in format

## OJ exercise of complexity

### 1. Disappearing figures

Title Description:

The array nums contains all integers from 0 to N, but one of them is missing. Please write code to find the missing integer. Do you have a way to finish it in O(n) time?

Example 1:

Input: [3,0,1]
Output: 2

Example 2:

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

Title Source: Disappearing numbers

Solution 1:

Sort first, and then find out whether the previous number + 1 is equal to the next number. If it is equal to, continue. If it is not equal to this number, it is the missing number

However, the complexity does not meet the requirements. qsort fast scheduling, time complexity O(N*logN), and the title requirement is O(n), so let's look at the next solution:

Solution 2:

Sum, loop to calculate 0 + 1 + 2 +... + n, subtract the values in the array, and the accumulation is the missing number

The code is as follows:

```int missingNumber(int* nums,int numssize)
{
int i=0;
int sum=0;
int sum1=0;
for(i=0;i<numssize;i++)
{
sum+=nums[i];
}
for(i=1;i<=numssize;i++)
{
sum1+=i;
}

return sum1-sum;
}
```

First calculate the sum of all the numbers in the array, and then calculate the sum of 0-numsize. Subtraction is the missing number.

Solution 3:

Before we look at the idea of solution 3, we need to know that two identical number XORs are equal to 0, 0 and any number XOR is equal to itself

For example, 3 exclusive or 3, the difference is 1, and their binary bits are the same, so they are all 0, so they are equal to 0

Solution 3 idea:

Create a variable x=0. X first follows the XOR of the value in the array, and then follows the XOR of the number between 0-n. it is equivalent to that other numbers appear twice. The XOR of both times becomes 0, and the missing number only appears once. Therefore, it is best that x is the missing number

Time complexity O(N), meeting the requirements

The code is as follows:

```int missingnumber(int* nums,int numssize)
{
int x=0;
//XOR with the value of the array first
for(int i=0;i<numssize;i++)
{
x^=nums[i];
}
//Then XOR with the number 0-n
for(int i=0;i<=numssize;i++)
{
x^=i;
}
return x;
}
```

### 2. Rotate array

Title Description:

Given an array, move the elements in the array K positions to the right, where k is a non negative number.

Think of as many solutions as possible. There are at least three different ways to solve this problem.
Can you use the in-situ algorithm with spatial complexity O(1) to solve this problem?

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
Rotate one step to the right: [7,1,2,3,4,5,6]
Rotate 2 steps to the right: [6,7,1,2,3,4,5]
Rotate 3 steps to the right: [5,6,7,1,2,3,4]

Title Source: Rotate array

Solution 1:

Rotate right once: keep the last value to the temp variable, move the value of the array to the right once, and then put temp to the far left

Then set a layer of circulation on the outside, right-handed k times

Time complexity: 0 (n (k% n)) - > when K==N, the time complexity is O(1), and the worst is O(N^2). When K==N-1, the time complexity considers the worst case, so the time complexity is O(N^2). The time performance of this method is not high*

Space complexity is O(1)

The code is as follows:

```void rotate(char*str,int k)
{
int i=0;
int len=strlen(str)
for(i=0;i<k%len;i++)
{
char temp=str[len-1]
int j=0;
for(j=len-1;j>0;j--)
{
str[j]=str[j-1];
}
str[0]=temp;
}
}
```

What needs to be considered here is that when k is equal to len, it is equivalent to no rotation, so the termination condition of the external for loop here is I < K% len.

Solution 2:

Idea:

This is the solution of space for time, using two arrays: directly put the last K on the first k of the second array, and the first n-k on the back of the second array

The code is as follows:

```int main()
{
int arr1[] = { 1,2,3,4,5,6,7 };
int arr2[10] = { 0 };
int k = 0;
scanf("%d", &k);
int sz = sizeof(arr1) / sizeof(arr1[0]);
int i = 0;
//Put the last K numbers on the first k of the second array
for (i = 0; i < k; i++)
{
arr2[i] = arr1[sz - k + i];
}
//Put the first n-k numbers after the second array
for (i = 0; i < sz - k; i++)
{
arr2[k + i] = arr1[i];
}
for (i = 0; i < sz; i++)
{
printf("%d ", arr2[i]);
}
return 0;
}
```

Time complexity: O(N)

Space complexity: O(N)

This can solve this problem, but this OJ question cannot be written like this, because this OJ question is interface type:

We put the elements of array 1 in array 2. We didn't change the rotation of array 1, but put the rotation result of array 1 in array 2. Moreover, the return value of this function is void, and we can't return array 2. It's good if we have this idea. This is a solution, but it can't be passed.

Let's look at solution 3. This is the optimal solution

Solution 3: three step turnover method

1. Invert the first n-k numbers

2. Inverse of the last k numbers

3. Global inversion

```void reverse(int *nums,int begin,int end)
{
while(begin<end)
{
int temp=nums[begin];
nums[begin]=nums[end];
nums[end]=temp;
begin++;
end--;
}
}
void rotate(int *nums,int numssize,int k)
{
k%=numssize;
reverse(nums,0,numssize-k-1);
//Invert the first n-k numbers
reverse(nums,numssize-k,numssize-1);
//Inverse of the last k numbers
reverse(nums,0,numssize-1);
//Global inversion
}
```

The time complexity of this solution: O(N) and space complexity: O(1) are optimal. It is recommended that you write the third solution, and the code is not difficult. You only need to write an inverse function. You only need to pay attention to the clear grasp of the first n-k and last K parameters when transmitting inverse parameters.

Let's look at some OJ questions in the sequence table array:

## Array related OJ questions

### 1. Remove element

Title Description:

Give you an array num and a value val. you need to remove all elements with a value equal to Val in place and return the new length of the removed array.

Instead of using extra array space, you must use only O(1) extra space and modify the input array in place.

The order of elements can be changed. You don't need to consider the elements in the array that exceed the new length.

Title Source: Removing Elements

Remove all elements val in the array in place. The time complexity is O(N) and the space complexity is O(1)

Idea 1:

Traverse the array, encounter the val value, move the following data to a unit and delete it

Time complexity: O(N^2)

Space complexity: O(1)

```int removeElement(int* nums, int numsSize, int val)
{
int i = 0;
int temp = numsSize;
//1234546
for (i = 0; i < numsSize; i++)
{
if (nums[i] == val)
{
int begin = i;
while (begin<numsSize-1)
{
nums[begin] = nums[begin + 1];
begin++;
}
temp--;//Number of current elements of the array
i--;
numsSize--;
}
}
return temp;
}
//Test code
int main()
{
int nums[]={1,2,3,4,5,4,6};
int numsSize=sizeof(nums)/sizeof(nums[0]);
int ret = removeElement(nums,numsSize,4);
for(int i=0;i<ret;i++)
{
printf("%d ",nums[i]);
}
return 0;
}
```

After moving the data every time, we need to move i –. At this time, the i value of the subscript is the subscript of val, and the elements behind val move forward. At this time, the i subscript corresponds to the next element of val, so we should keep i unchanged and continue to traverse. At the same time, the number of traversals should be less to prevent crossing the boundary. We should also let numsize –, temp record the number of elements.

Idea 2:

Space for time: copy all values that are not 3 in the original array to the new array, and then copy them back. The time complexity O(N) and space complexity O(N) only do not meet the requirements of the question, because the space complexity of the question requires O(N)

We can only know this idea here. This idea cannot solve this problem, because the complexity of the topic space requires O(N). The test code of idea 2 is as follows:

```int removeElement(int* nums1, int* nums2, int numsSize, int val)
{
int i = 0;
int temp = 0;
for (i = 0; i < numsSize; i++)
{
if (nums1[i] != val)
{
nums2[i] = nums1[i];
temp++;
}
else
{
nums2--;
}
}
return temp;
}
int main()
{
int nums1[] = { 1,2,3,4,5,4,6 };
int nums2[8] = {0};//1,2,3,5,6
int numsSize = sizeof(nums1) / sizeof(nums1[0]);
int ret = removeElement(nums1, nums2, numsSize, 4);
for (int i = 0; i < ret; i++)
{
printf("%d ", nums2[i]);
}
return 0;
}
```

The best idea is given below:

Idea 3:

Give two pointers dest and src to point to the starting position. src finds the position that is not val and puts it at the position pointed by dest. Time complexity: O(N), space complexity: O(1)

src stops when pointing out of the array, and then returns dest, which happens to be the array after deleting the val value

The code is as follows:

```int removeElement(int *nums,int numsSize)
{
int src=0,dest=0;
while(src<numssize)
{
if(nums[src]==val)
{
src++;
}
else
{
nums[dest]=nums[src];
src++;
dest++;
}
}
return dest;
}
```

### 2. Delete duplicate values in the ordered array

Title Description:

Give you an ordered array nums, please delete the repeated elements in place, make each element appear only once, and return the new length of the deleted array.

Do not use additional array space. You must modify the input array in place and complete it with O(1) additional space.

Example 1:

Input: num = [1,1,2]
Output: 2, Num = [1,2]
Explanation: the function should return a new length of 2, and the first two elements of the original array num are modified to 1 and 2. There is no need to consider the elements in the array that exceed the new length.

Example 2:

Input: num = [0,0,1,1,1,2,2,3,3,4]
Output: 5, Num = [0,1,2,3,4]
Explanation: the function should return a new length of 5, and the first five elements of the original array num are modified to 0, 1, 2, 3 and 4. There is no need to consider the elements in the array that exceed the new length.

Title Source: Removes duplicate values from an ordered array

Idea:

src finds a value that is not equal to dest. src + + is not found. Dest + + is found. Put src into dest and then src++

The code is as follows:

```int removeDuplicates(int* nums, int numsSize){
int src=0;
int dest=0;
if(numsSize==0)
{
return 0;
}
while(src<numsSize)
{
if(nums[src]==nums[dest])
{
src++;
}
else
{
dest++;
nums[dest]=nums[src];
src++;
}
}
return dest+1;//Returns the length of the array
}
```

### 3. Merge two ordered arrays

Title Description:

Here are two ordered integer arrays nums1 and nums2. Please merge nums2 into nums1 to make nums1 an ordered array. The number of elements initializing nums1 and nums2 is m and n, respectively. You can assume that the space size of nums1 is equal to m + n, so it has enough space to store elements from nums2.

Example 1:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]

Title Source: Merge two arrays

Idea:

Solution 1: copy nums2 data to nums1, qsort quickly arrange nums1, and the time complexity is (m+n)*log(m+n)

Solution 2: open up a new m+n array, merge two small arrays, compare the values of the two arrays from scratch, put the small array into the new array, and then copy it to nums1, time complexity O (m+n), space complexity O (m+n)

Solution 3: take the larger one in turn and put it into nums1 from back to front

Here we explain solution 3:

After the above analysis, the code is as follows:

```void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
int i1 = m-1,i2 = n-1;
int dest=m+n-1;
while(i1>=0 && i2>=0)//Continue when both are greater than or equal to 0
{
if(nums1[i1]>nums2[i2])//Take the big one and put it behind nums1
{
nums1[dest--]=nums1[i1--];
}
else
{
nums1[dest--]=nums2[i2--];
}
}
//If I2 < 0 and nums2 copy ends, the processing ends, because the remaining number is already in nums1

//If nums1 ends, move the data of nums2
while(i2>=0)
{
nums1[dest--]=nums2[i2--];
}

}
```

It should be noted that:

If I2 < 0 and nums2 copy ends, the processing ends, because the remaining number is already in nums1

If nums1 ends, move the data of nums2

How do we analyze OJ procedures when OJ reports errors?

• If not, first get used to reading the code with the test cases it reports errors to

• Copy the code to vs, supplement other codes, and test with unprecedented tests

### 1. Remove linked list elements

Title Description:

Title Source: Remove linked list elements

Idea 1: insert the end of all values in the linked list that are not Val into the new linked list and delete nodes equal to val

Train of thought analysis:

In addition, we need to consider the case that the head passed in is NULL. If the head is NULL, we directly return NULL

The code of idea 1 is as follows:

```struct ListNode* removeElements(struct ListNode* head, int val)
{
{
return NULL;
}
//val deletes it, not inserts the tail of val into the new linked list
while(cur)
{
struct ListNode* next=cur->next;//It is convenient to find the next node of the current node and define a next
if(cur->val==val)//Yes val delete
{
free(cur);
}
else//Not for tail insertion
{
//When tail is NULL, there is no element
if(tail==NULL)//Trailing first element
{
tail=cur;
}
else
{
tail->next=cur;
tail=cur;
}
}
cur=next;
}
//When the data of the last node in the linked list is val and the previous node is not val, we insert the tail of the previous node into the new linked list and delete the last node. However, we do not set the next of the previous node to NULL, so we need to empty it here; And we need to judge whether the tail is NULL or not before we can perform this operation. When the val values of the linked list are all the val values specified for deletion, there is no tail inserted into the new linked list element. At this time, the tail is NULL, so we can't set the next of the tail to NULL
if(tail)
{
tail->next=NULL;
}
}
```

It should be noted that:

When the data of the last node in the linked list is val and the previous node is not val, we insert the tail of the previous node into the new linked list and delete the last node. However, we do not set the next of the previous node to NULL, so we need to empty it here; And we need to judge whether the tail is NULL or not before we can perform this operation. When the val values of the linked list are all the val values specified for deletion, there is no tail inserted into the new linked list element. At this time, the tail is NULL, so we can't set the next of the tail to NULL

Idea 2: cur finds the node where val is located, prev records the previous node, and deletes the linked list. To delete the linked list, you need to find the previous node of the deleted node

```struct ListNode* removeElements(struct ListNode* head, int val)
{
{
return NULL;
}
while (cur)
{
while ( cur && (cur->val) != val )
{
prev = cur;//Record the previous node of the current node
cur = cur->next;
}
//There are two situations when "while" comes out: 1. Cur is NULL, which means that it is over. 2. (cur - > VAL) = = Val, which should be deleted at this time
if(cur==NULL)
{
}
//Find val, delete

if (cur == head)//If the first value is val, delete the header
{
free(cur);
}
else//Subsequent deletion
{
prev->next = cur->next;
free(cur);
cur = prev->next;
}

}
}
```

Define a cur and prev to traverse. Prev records the previous node of cur. Cur is not empty. Enter the loop, and then use a loop to find the node with val value. When it comes out, there are two situations: 1. Cur is NULL, indicating that it is over. 2. (cur - > val) = = val, which should be deleted at this time; Therefore, it is necessary to judge whether cur is NULL. If cur is NULL, it will directly return to head. Otherwise, the node will be deleted, and the deletion will be divided into header deletion and non header deletion.

Title Description:

**Idea 1: * * adjust the direction of node pointer, reverse the direction of n1 and n2, and iterate with n3

When n2 is NULL, n1 can be returned, but there is a problem. If n2 - > next = n1, how can we find the next node of n2? Here, we also need to use an n3 node to save the previous n2 next

```struct ListNode* reverseList(struct ListNode* head)
{
{
return NULL;
}
struct ListNode* n1,*n2,*n3;
n1=NULL;

while(n2)
{
n2->next=n1;
n1=n2;
n2=n3;
if(n3)//When n3 is NULL, n3 has no next
{
n3=n3->next;
}
}
return n1;
}
```

Idea 2:

Head interpolation method: define a new linked list, newhead=NULL, the original linked list defines cur and next, and next records the next node of cur

```struct ListNode* reverseList(struct ListNode* head)
{
{
return NULL;
}
struct ListNode* next=cur->next;

while(cur)
{
next=cur->next;
cur=next;
}
}
```

### 3. Find the middle node of a linked list

Title Description:

Given a non empty single linked list with head node, return the intermediate node of the linked list.

If there are two intermediate nodes, the second intermediate node is returned.

Example 1:

Input: [1,2,3,4,5]
Output: node 3 in this list (serialized form: [3,4,5])
The returned node value is 3.
Example 2:

Input: [1,2,3,4,5,6]
Output: node 4 in this list (serialized form: [4,5,6])
Since the list has two intermediate nodes with values of 3 and 4, we return the second node.

Title Source: Find the middle node of a linked list

Idea:

Using fast and slow pointers

slow one step at a time

fast takes two steps at a time

When fast comes to the end, slow comes to the middle node

Slow takes one step at a time and fast takes two steps at a time. When fast comes to the end, slow goes to the middle node

But what about the even number of nodes? The requirement of the topic is to return: if there are two intermediate nodes, return the second intermediate node.

After drawing and understanding, it is found that:

When fast reaches NULL, slow reaches the second intermediate node.

Therefore, the condition for loop termination should be that fast is not NULL and fast - > next is not NULL

The problem solving code is as follows:

```struct ListNode* middleNode(struct ListNode* head)
{
{
return NULL;
}
//Speed pointer
while(fast&&fast->next!=NULL)
{
slow=slow->next;
fast=fast->next->next;
}
return slow;
}
```

### 4. The penultimate node in the lin k ed list

Title Description:

Input a linked list and output the penultimate node in the linked list.

Example 1

Input:

```1,{1,2,3,4,5}
```

Return value:

```{5}
```

Title Source: Find the middle node of a linked list

Idea:

Like the above question, we first define two pointers slow, fast, fast, take step k first, and then go together. Let's look at the following dynamic diagram:

When fast is NULL, the slow is the penultimate node

It should be noted that if the input k is greater than the number of nodes, fast will become NULL before K steps are completed. In particular, NULL should be returned here

```struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
{
if(k==0)
{
return NULL;
}
struct ListNode*slow,*fast;
//fast k steps first
while(k--)
{
if(fast==NULL)//The input k is greater than the number of nodes, and fast becomes NULL before it has finished K steps
{
return NULL;
}
fast=fast->next;
}
while(fast)
{
slow=slow->next;
fast=fast->next;
}
return slow;
}
```

When fast takes K steps first, if the input k is greater than the number of nodes, fast will become NULL before it has finished K steps. Here, it is necessary to judge whether fast is equal to NULL. If it is equal to NULL, it will directly return NULL.

### 5. Merge two ordered linked lists

Title Description:

Merge the two ascending linked lists into a new ascending linked list and return. The new linked list is composed of all nodes of a given two linked lists.

Idea: take a small node and insert it into the new linked list

According to the analysis, our code is as follows:

```struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{
//If l1 is NULL, l2 is returned
if(l1==NULL)
{
return l2;
}
//If l2 is NULL, l1 is returned
if(l2==NULL)
{
return l1;
}
struct ListNode*tail=NULL;//Record the end of the new linked list
struct ListNode* n1=l1;
struct ListNode* n2=l2;
while(n1&&n2)
{
//Compare the val of n1 and n2 and insert the small tail in the new linked list
if(n1->val<n2->val)
{
//When the new linked list is NULL, that is, when there are no nodes
if(tail==NULL)
{
}
//When it is not NULL, there are nodes
else
{
tail->next=n1;
tail=n1;
}
n1=n1->next;//At this time, the smaller tail has been inserted into the new linked list, and the iteration is carried out here
}
else
{
if(tail==NULL)
{
}
else
{
tail->next=n2;
tail=n2;
}
n2=n2->next;
}
//Ends when n1 or n2 is NULL
}
//Link the remaining nodes that are not NULL to the tail of the new linked list
if(n1)
{
tail->next=n1;
}
if(n2)
{
tail->next=n2;
}
}
```

So can we optimize it?

Since we need special treatment when inserting n1 or n2 into a new linked list for the first time, we can insert a node into it outside first. There is no need to recycle it here. The tail insertion when there is no node should be considered in if and else. The code is as follows:

```struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{
if(l1==NULL)
{
return l2;
}
if(l2==NULL)
{
return l1;
}
struct ListNode*tail=NULL;
struct ListNode* n1=l1;
struct ListNode* n2=l2;
if(n1->val<n2->val)
{
n1=n1->next;
}
else
{
n2=n2->next;
}
while(n1&&n2)
{
if(n1->val<n2->val)
{
//Tail insert n1
tail->next=n1;
tail=n1;
n1=n1->next;
}
else
{
//Tail insertion n2
tail->next=n2;
tail=n2;
n2=n2->next;
}
}
if(n1)
{
tail->next=n1;
}
if(n2)
{
tail->next=n2;
}
}
```

Another method does not need to consider the case that the new linked list is NULL during tail insertion, that is, we set a head node with sentry position. Let's introduce it below:

For the head node with sentinel bit, this node does not store valid data, and the function will never be modified to the pointer plist pointing to the first node storing valid data, because with this head node with sentinel bit, when inserting and deleting the first node in front of the first element node, its operation is unified with that of other nodes.

The head node with sentinel position looks a little simpler. Why doesn't our single linked list design this structure?

The structure of this head node rarely appears in practice, including hash bucket and adjacency table as substructures. Secondly, the linked list given in OJ basically does not take the lead.

Head node method with sentry position:

```struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{
if(l1==NULL)
{
return l2;
}
if(l2==NULL)
{
return l1;
}
struct ListNode*tail=NULL;
while(l1&&l2)
{
if(l1->val<l2->val)
{
//Tail insert l1
tail->next=l1;
tail=l1;
l1=l1->next;
}
else
{
//Tail insertion l2
tail->next=l2;
tail=l2;
l2=l2->next;
}
}
if(l1)
{
tail->next=l1;
}
if(l2)
{
tail->next=l2;
}

//return newhead->next; Directly return this will cause a memory leak
return first;
}
```

It should be noted that we need to release the opened head node with sentinel bit at last, otherwise there will be memory leakage. We need to return the next of newhead. Then we use first to save the next of newhead, and then free the newhead

Title Description:

There is a header pointer ListNode pHead of a linked list. Given a certain value of X, write a piece of code to rank all nodes less than x before the other nodes, and the original data order cannot be changed. Return the header pointer of the rearranged linked list*

Idea:

1. Insert the tail smaller than x into a linked list

2. Insert the tail larger than x into a linked list

The code is as follows:

```ListNode* partition(ListNode* pHead, int x)
{
// write code here
struct ListNode* GreaterHead=(struct ListNode*)malloc(sizeof(struct ListNode));//Node with sentinel position head with larger value
while(cur)
{
if(cur->val<x)
{
//The tail is inserted into the linked list storing smaller values
LessTail->next=cur;
LessTail=cur;
}
else
{
//The tail is inserted into the linked list storing large values

GreaterTail->next=cur;
GreaterTail=cur;
}
cur=cur->next;
}
GreaterTail->next=NULL;

return first;
}
```

### 7. Palindrome structure of linked list

Title Description:

For a linked list, please design an algorithm with time complexity of O(n) and additional space complexity of O(1) to judge whether it is palindrome structure.

Given the header pointer A of A linked list, please return A bool value to represent whether it is A palindrome structure. Ensure that the length of the linked list is less than or equal to 900.

Test example:

```1->2->2->1
return: true

1->2->3->2->1
return: true

```

Title Source: Palindrome structure of linked list

Idea 1:

Define an array, copy all val values in the linked list, and then compare whether the first and last are equal by subscript

```bool chkPalindrome(ListNode* A) {
// write code here

int a[900];
struct ListNode* cur=A;
int n=0;
while(cur)
{
a[n++]=cur->val;
cur=cur->next;
}
int left=0;
int right=n-1;
while(left<right)
{
if(a[left]!=a[right])
{
return false;
}
left++;
right--;
}
return true;
}
```

The spatial complexity of this solution is O(n), and the spatial complexity does not meet the requirements, but niuke.com has given it. Some OJ problems have the requirements of time complexity and spatial complexity, but the inspection of background test cases is not easy to check the time complexity and spatial complexity. For the complexity, the OJ system is usually not very strict. This piece of leetcode will be stricter and more loose, including the integrity of test cases.

Let's look at a correct solution:

Idea 2:

1. Find the intermediate node first

2. Reverse the second half

3. Compare the first half and the second half

We have talked about finding intermediate nodes and inverse linked lists before. The rest is to compare the first half and the second half

The code is as follows:

```struct ListNode* FindMidNode(struct ListNode* phead)//Find intermediate node
{
struct ListNode*slow,fast;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next;
}
return slow;
}

//Pass the first level pointer and return the header pointer with the return value
{
while(cur)
{
struct ListNode*next=cur->next;
cur=next;
}
}*/

//Pass the secondary pointer and modify the header pointer in the function
{
{
struct ListNode*next=cur->next;
cur=next;
}

bool chkPalindrome(ListNode* A)
{
struct ListNode*mid = FindMidNode(A);
{
return false;

}
return true;
}
```

### 8. Intersection of linked lists

Title Description:

As shown in the figure, two linked lists intersect at node c1:

The title data ensures that there are no rings in the whole chain structure.

Note that after the function returns the result, the linked list must maintain its original structure.

Title Source: Intersection of linked lists

How to determine whether A and B linked lists intersect?

Idea 1:

Conventional idea: each node of A linked list is compared with all nodes of b linked list in turn. If there is an equal node, it is the intersection. The time complexity is O(N^2)

Optimization idea: calculate the length of A and B, lenA and lenB respectively, let the long one take the "lenA lenB" step first, and then compare to find the intersection. The time complexity is O(N)

Idea 2: judge whether the last node is the same

The problem requires us to return to the intersecting nodes, so we use the optimization idea of idea 1 to solve the problem:

The code is as follows:

```struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
int lenB=0;
int lenA=0;
while(curA)//Calculate the length of A
{
lenA++;
curA=curA->next;
}
while(curB)//Calculate the length of B
{
lenB++;
curB=curB->next;
}
//Suppose A is long and B is short
if(lenA<lenB)
{
}

//Let the long take the first step
int gap=abs(lenA-lenB);
while(gap--)
{
longList=longList->next;
}
//Go at the same time and find the intersection
while(longList && shortList)
{
if(longList == shortList)
{
return longList;//Found return
}
longList=longList->next;
shortList=shortList->next;
}

//Indicates disjoint
return NULL;
}
```

First, we calculate the length of A and B linked lists. Then we assume that the long linked list is A and the short one is B. then, if Lena < lenb, we assign B to the long linked list and A to the short linked list. Then we let the long ones go first, and finally go together, and then find the intersection

Problem Description:

If there is a node in the linked list that can be reached again by continuously tracking the next pointer, there is a ring in the linked list. In order to represent the rings in a given linked list, we use the integer pos to represent the position where the tail of the linked list is connected to the linked list (the index starts from 0). If pos is - 1, there are no rings in the linked list. Note: pos is not passed as a parameter, but only to identify the actual situation of the linked list.

Returns true if there are links in the linked list. Otherwise, false is returned.

Can you solve this problem with O(1) (i.e., constant) memory?
Example 1:

```Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: there is a ring in the linked list, and its tail is connected to the second node.
```

Example 2:

```Input: head = [1,2], pos = 0
Output: true
Explanation: there is a ring in the linked list, and its tail is connected to the first node.
```

Example 3:

```Input: head = [1], pos = -1
Output: false
```

Idea:

Fast and slow pointer, slow pointer takes one step at a time. The fast pointer takes two steps at a time. If the fast pointer can be equal to the slow pointer, it is a circular linked list, otherwise it is not

The code is as follows:

```bool hasCycle(struct ListNode *head) {
struct ListNode *slow,*fast;
while(fast && fast->next)
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
{
return true;
}
}
return false;
}
```

The code of this question is very simple, but the examination of this question in the interview may not only let you write the code, but the interviewer may ask:

Interview questions:

• slow one step at a time, fast two steps at a time? Can we catch up? Please prove that:

It must be possible to catch up. When slow enters the ring, fast has walked a certain length in the ring, and then a chase is formed in the ring. Fast goes to catch up with slow. Suppose that when slow enters the ring, the distance between fast and slow is N and the size of the ring is C, then N must be less than C

In catching up, slow takes one step at a time and fast takes two steps at a time

The distance change between fast and slow is:

N,N-1,N-2,N-3...2,1,0

N must be reduced to 0 at last, so if the distance is 0, it must meet

Slow enters the ring. Within one circle, fast will catch up with slow

• slow takes one step at a time, fast takes n steps at a time, n > (2,3,4,5...), OK? Firstly, the size of the ring and the length in front of the ring are uncertain. Please prove that:

Not necessarily catch up

Suppose slow takes one step at a time and fast takes three steps at a time. When slow enters the loop, the gap between them is N and the length of the loop is C

The distance between fast and slow varies as follows:

N,N-2,N-4,...,

When the distance between slow and fast is 0, it will catch up, so it means that N is an even number, and it will catch up

If N is an odd number and C-1 is an odd number, it will never catch up

When fast reaches the distance of - 1, their distance is C-1. When C-1 is also an odd number, they will never catch up

Conclusion: it's OK for fast to take x steps at a time and slow to take y steps at a time. The most important thing is that if the step difference in the process of catching up is x-y and the step difference is 1, we can catch up with others

### 10. Circular linked list II

Title Description:

Given a linked list, return the first node from the linked list into the ring. If the linked list is acyclic, null is returned.

In order to represent the rings in a given list, we use the integer pos to represent the position where the tail of the list is connected to the list (the index starts from 0). If pos is - 1, there is no ring in the list. Note that pos is only used to identify the ring and will not be passed to the function as a parameter.

Note: it is not allowed to modify the given linked list.

Can you use O(1) space to solve this problem?

Title Source: Circular linked list II

Solution idea 1:

One pointer starts from the meeting point and the other pointer starts from the head. They will meet at the entry point

prove:

Suppose: the distance from the chain header to the entry point is L, the distance from the encounter point to the entry point is X, and the length of the ring is C,

The distance of the slow pointer is L+X

The fast pointer goes L+C+X

2(L+X)=L+C+X, L=C-X*

The proof of many articles is this, but this proof is wrong, because fast does not necessarily walk only once in the ring before slow enters the ring

Correct proof

When meeting: the distance taken by the slow pointer is L+X

Fast pointer distance L+NC+X (n > = 1)

2(L+X)=L+NC+X

L+X=NC

L=NC-X

L=(N-1)C+C-X

Conclusion: a pointer starts from the meeting point and a pointer starts from the head. They will meet at the entry point

Problem solving idea 2:

Break the meet point, then judge the intersection and return to the intersection

The code is as follows:

``` struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
//1. Calculate the length of A and B
int lenA=0;
int lenB=0;
while(curA)
{
lenA++;
curA=curA->next;
}
while(curB)
{
lenB++;
curB=curB->next;
}
//2. Calculate the length difference, and take the difference step first
int gap = abs(lenA-lenB);
if(lenA<lenB)
{
}
while(gap--)
{
longList=longList->next;
}
//3. Then go together
while(longList && shortList)
{
if(longList==shortList)
{
return longList;
}
longList=longList->next;
shortList=shortList->next;
}
return NULL;
}

struct ListNode *detectCycle(struct ListNode *head) {
while(fast &&fast->next)
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
{
//Met
struct ListNode *meet=slow;
struct ListNode *next=meet->next;//Record the next node at the meeting point
meet->next=NULL;//Disconnect the meeting point
}
}
return NULL;
}
```

### 11. Copy the linked list with random pointer

Title Description:

Give you a linked list with a length of n. each node contains an additional random pointer random, which can point to any node or empty node in the linked list.

Construct a deep copy of this linked list. The deep copy should consist of exactly n new nodes, in which the value of each new node is set to the value of its corresponding original node. The next pointer and random pointer of the new node should also point to the new node in the replication linked list, and these pointers in the original linked list and the replication linked list can represent the same linked list state. The pointer in the copy linked list should not point to the node in the original linked list.

For example, if there are two nodes X and Y in the original linked list, where x.random -- > y. Then, the corresponding two nodes X and Y in the copy linked list also have x.random -- > y.

Example 1

Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

Output: [[1,1], [2,1]]

Example 3:

Output: [[3,null],[3,0],[3,null]]

Example 4:

Output: []
Explanation: the given linked list is null (null pointer), so null is returned.

Title Source: Copy linked list with random pointer

Idea 1:

1. First copy each node of the original linked list and link the copied new nodes

2. Calculate the relative distance between the random and cur of each node in the original linked list

Then copy the node with the relative distance from the new linked list to the current node, assign it to random, find the random time complexity of each node is O(N), and N nodes are O(N^2) - low efficiency

Idea 2:

1. After each node of the original linked list, the link inserts a copy node

2. Set random

3. Cut out the copy nodes, link them together, and restore the original linked list at the same time

The code is as follows:

```struct Node* copyRandomList(struct Node* head) {
{
return NULL;
}
//1. The copy of each node is linked behind that node
while(cur)
{
struct Node* next = cur->next;
struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
copy->val=cur->val;
cur->next=copy;
copy->next=next;
cur=next;
}
//2. Set random
while(cur)
{
struct Node* copy=cur->next;
if(cur->random)
{
copy->random = cur->random->next;
}
else
{
copy->random=NULL;
}
cur=copy->next;
}
//3. Cut the copied node and insert the tail into the new linked list
while(cur)
{
struct Node* copy=cur->next;
struct Node* next=copy->next;
tail->next=copy;
tail=copy;

cur->next=next;
cur=next;
}