## 1. Invert (reverse) the node after the pp node in the linked list.

Solution ideas:
Set two pointers ss\ssnext. One ss pointer points to the next node of the pp node. Set the node behind the pp pointer to null, leaving the elements in the list in front of the pp node. Then use the other set pointer ssnext to save the information of the next node of the ss pointer. Then insert the node pointed by ss into the back of the pp node. The ss pointer then points to the next node until the ss pointer is null.

```//1. Invert (reverse) the node after the pp node in the linked list.
void ReverseList(LNode *pp)
{
LNode *ss,*ssnext;//Set two pointers ss\ssnext.

ss=pp->next;//The ss pointer points to the next node of the pp node.
pp->next=NULL;//Set the node behind the pp pointer to null, leaving the elements in the list before the pp node.

while(ss!=NULL)
{
ssnext=ss->next;//The ssnext pointer stores the information of the next node of the ss pointer.

//Insert the node pointed by ss into the back of pp node.
ss->next=pp->next;
pp->next=ss;

ss=ssnext;//The ss pointer then points to the next node.
}
}
```

## 2. Reverse print all the elements in the linked list.

Solution ideas:
Using recursive implementation, when the pointer does not point to the end of the table, it will always call its own function until the pointer returns empty, and the output statement will be executed from the end of the linked list to the front. The time complexity is O(n).

```//2. Reverse print all the elements in the linked list.
void PrintList1(LNode *pp)
{
if(pp == NULL) return;//It is determined whether the pointer is empty.

PrintList1(pp->next);//Call its own function.

printf("%3d",pp->data);//Output statement.
}
```

## 3. Find the penultimate K (k > 0) node of the single chain list of the leading node.

Solution ideas:
Two pointers can be set, one starting first is set as fast pointer, and the other starting later is set as slow pointer. First, let the fast pointer move from the header to the positive k-th node, and then set the other slow pointer to keep the same speed as the starting pointer and move backward until the fast pointer moves to the end of the table. At this time, the slow moving position is the position of the table length minus K, that is, the penultimate K position.

```//3. Find the penultimate K (k > 0) node of the single chain list of the leading node.
{
LNode *fast=LL;//Set a fast pointer that starts first.
int ii=0;
while((fast!=NULL)&&(ii<kk))
{
fast=fast->next;//The fast pointer moves to the k th node.
ii++;
}
if(fast == NULL) return NULL;//When the fast pointer is equal to null, it indicates that the table length is less than k and returns null.

LNode *slow=LL->next;//Set a slow pointer for the backward departure.
while(fast!=NULL)//When the fast pointer moves to the end of the table, the slow pointer just moves to the k-th node
{
slow=slow->next;
fast=fast->next;
}

return slow;
}
```

## 4. Judge whether the single chain list has a ring and find the entry of the ring.

Solution ideas:
Idea 1:
The slow pointer takes one step, and the fast pointer takes two steps. The speed of the fast pointer is twice that of the slow pointer. When the distance of the fast pointer is twice that of the slow pointer, they will meet.
Note that when looking for the entrance of the ring, we need to calculate: let the distance from the head to the entrance of the ring be len, and the circumference of the ring be peri. After the slow pointer enters the ring with the length of x, it meets the fast pointer, and the fast pointer meets the slow pointer after passing through the n-ring.
Given that the distance of the fast pointer is twice the distance of the slow pointer, we can obtain:
len+n* peri+x=2 * (len+x) we can get: len=n*peri-x, so after the fast and slow pointers meet, set another pointer to start from the header, keep the same speed as the slow pointer, and the two pointers will meet at the ring entrance.
Illustration:

```//4. Judge whether the single chain list has a ring and find the entry of the ring.
{
LNode *fast,*slow;//Set the speed pointer.
fast=LL;
slow=LL;
while(fast!=NULL)
{
fast=fast->next->next;//The fast pointer takes two steps.
slow=slow->next;//The slow pointer moves one step.
if(slow == fast) break;//When the distance of the fast pointer is twice that of the slow pointer, they will meet.
}
if(fast == NULL) { printf("The linked list has no ring!\n"); return NULL; }//When the fast pointer fast reaches the end of the list, it is proved that the linked list has no ring.

//Look for the entrance to the ring.
LNode *enter=LL;//Set a pointer to the head node.

while(slow!=enter)
{
slow=slow->next;
enter=enter->next;
}

return enter;
}
```

Idea 2:
It can also traverse the nodes it passes through through every step of the pointer. If the same node is found, it is proved that the linked list has a ring, and the entry of the ring is the same node found. The time complexity is O(n^2)

## 5. Find the common nodes of the two aggregation single linked lists. If there is no aggregation, return null. If there is, return the first node of the aggregation.

Solution ideas:
To solve this problem, you can first find the difference n between the lengths of the two linked lists, then move the pointer of the longer linked list from the beginning by N nodes, and then move the pointer of the shorter linked list and the pointer of the longer linked list at the same time until you find the convergence point or the tail of one of the linked lists. The time complexity is O(n).

```//5. Find the common nodes of the two aggregation single linked lists. If there is no aggregation, return null. If there is, return the first node of the aggregation.
//First write a function to find the length of the linked list.
// Find the length of the linked list, return value: > = 0 - the number of LL nodes in the table.
{
if (LL == NULL) { printf("Linked list LL non-existent.\n"); return 0; } // It is determined whether the linked list exists.

LNode *pp=LL->next;  // Start from the next node of the head node.

int length=0;

while (pp != NULL) { pp=pp->next; length++; }

return length;
}

{
int lena,lenb,len;//Define three integer variables, which are the length of La and LB linked lists, and len is the difference between the lengths of the two linked lists.
lena=LengthList(La);
lenb=LengthList(Lb);

len=lena-lenb;//Find the difference between the lengths of the two linked lists.

while(lena>lenb&&len>0)
{// Link list length La > LB
La=La->next;
len--;
}
while(lenb>lena&&len<0)
{// Link list length La < LB
Lb=Lb->next;
len++;
}

while(La!=Lb&&La!=NULL&&Lb!=NULL)
{
La=La->next;
Lb=Lb->next;
}
if(La == NULL||Lb == NULL) return NULL;

if(La == Lb) return La;
}
```

## 6. Change the linear table L=(a1,a2,a3,..., an-2,an-1,an) to L=(a1,an,a2,an-1,a3,an-2,...). The number of data nodes is even.

Title details:
Suppose that the linear table L=(a1,a2,a3,..., an-2,an-1,an) is stored in the single chain table of the leading node, and the number of data nodes is even.
Please design an algorithm with spatial complexity of O(1) and as efficient as possible in time to rearrange the nodes in L.
Finally, the linear table L=(a1,an,a2,an-1,a3,an-2,...) is obtained.
Solution ideas:
There are three steps to solve this problem. See the code for details.

```//6. Change the linear table L=(a1,a2,a3,...,an-2,an-1,an) to L=(a1,an,a2,an-1,a3,an-2,...). The number of data nodes is even.
{
if(LL == NULL) return;//The linked list is empty, exit the function.

//Step 1: set two pointers with different speeds. The fast pointer takes two steps and the slow pointer takes one step.
LNode *fast,*slow;
fast=LL;
slow=LL;

while(fast->next!=NULL)
{
fast=fast->next->next;
slow=slow->next;
}
//After the loop, fast stays at the last node of the linked list, and slow stays at the nth / 2nd node.

//Step 2: invert the node after the slow pointer in place.
//For example, A1, A2, A3, A4, A5, A6, a7, and A8 are inversed to A1, A2, A3, A4, A8, a7, A6, and A5
ReverseList(slow);//A user-defined function that reverses the node behind slow in place.

//Step 3: insert the node after the slow pointer into the middle of the previous node
LNode *front,*back,*tmp;
front=LL->next;//The front pointer points to the first data node of the linked list.
back=slow->next;//The bcak pointer points to the next node of the slow pointer

slow->next=NULL;//It is very important to leave only the first half of the linked list.

//Insert operation
while(back!=NULL)
{
tmp=back->next;//Use a temporary pointer variable to temporarily store the information of the next node after the back.

//Insert the back node into the previous node.
back->next=front->next;
front->next=back;

back=tmp;//The back pointer points back to the following node.
front=front->next->next;//Point the front to the position of the previous node where the next node needs to be inserted. Such as a1 to a2 in a1,a8,a2,a3.
}

/*
//Note: if the following code is used to loop, an error will occur, because slow is a pointer in the linked list.
LNode *pp,*tmp;
pp=LL->next;
slow=slow->next;

while(slow!=NULL);
{
tmp=slow->next;//This is equivalent to using tmp to point to the next node of the slow node;

//The next step is to insert the next node of the slow node after the pp node
slow->next=pp->next;pp->next=slow;

slow=tmp;//slow Point to the next node of slow
//That is, it points to the node inserted after pp, so the track of the slow pointer will continue to form a loop in the linked list and will never be empty.
pp=pp->next->next;
}
*/
}
```

Refer to learning video: Station B data structure learning video

Posted by shadownet on Mon, 15 Aug 2022 21:37:21 +0530