# The second phase of algorithm training-linked list

Posted Jun 27, 20204 min read

#### Offer 24. Reverse linked list

Simple difficulty 54

Define a function, input the head node of a linked list, invert the linked list and output the head node of the inverted list.

Example:

``````Input:1->2->3->4->5->NULL
Output:5->4->3->2->1->NULL``````

limit:

``0 <= number of nodes <= 5000``

Thought 1:

Although it is an exercise of a linked list, there are many ideas for the algorithm. I still said that I will use various methods, not the linked list part only to use the linked list

This question:Need to return a linked list pointer, this is a new linked list. This new list is essentially taking elements one by one from the end of the old list. That is to say, for the old linked list, it is actually a situation that comes out first. So the first thing that comes to our mind is the stack.

Push the stack from the beginning, and then push it out one by one. Put into a new linked list;

``````/**
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x):val(x), next(NULL) {}
* };
*/
class Solution {
public:
stack<ListNode*> stack_listnode;
}
ListNode* q = stack_listnode.top();
stack_listnode.pop();
while(stack_listnode.size() != 0) {
q->next = stack_listnode.top();
stack_listnode.pop();
q = q->next;
}
q->next = NULL;
}
};``````

Thought 2:

If you are a classmate who has seriously studied data structure, you will definitely think of a way:head interpolation and tail interpolation!

At this point, you must have understood. The head insertion and tail insertion will be detailed in another md;

Thought 3:

To put it simply, use two pointers to climb on a given linked list, assign values to the third pointer during the crawl, and slowly form the third pointer into a new linked list. A bit like the process of DNA transcription...

``````class Solution {
public:
ListNode *p1,*p2,*p3;
p1 = NULL;
while(p2!=NULL){
p3 = p2->next;
p2->next = p1;
p1 = p2;
p2 = p3;
}
return p1;
}
};``````

# Delete intermediate node

#### Interview Question 02.03. Delete Intermediate Node

Simple difficulty 31

Implement an algorithm to delete a node in the middle of the singly linked list(that is, not the first or last node), assuming that you can only access the node.

Example:

``````Input:singly linked list a->b->c->d->e->f node c
Result:No data is returned, but the linked list becomes a->b->d->e->f``````

Thinking:

The key to this question is to understand the meaning of the question.

Problem analysis:

The title only gives you a certain node, nothing else, and you can't get the linked list. Let you delete this element, personally think this is a good case. I can't get the linked list, only the node. I don t know which one it is...

But we can visit the nodes after this node, and we can also visit the nodes after. So make this node equal to the value of next, then delete next, steal the beam and replace the column.

How to delete? In fact, just assign node->next = node->next->next directly.

``````/**
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x):val(x), next(NULL) {}
* };
*/
class Solution {
public:
void deleteNode(ListNode* node) {
if(node   == NULL) return;
node->val = node->next->val;
node->next = node->next->next;
}
};``````

# Palindrome list

Simple difficulty 533

Example 1:

``````Input:1->2
Output:false``````

Example 2:

``````Input:1->2->2->1
Output:true``````

Can you solve this problem with O(n) time complexity and O(1) space complexity?

Thought 1:

Put into the array to compare one by one

``````/**
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x):val(x), next(NULL) {}
* };
*/
class Solution {
public:
vector<int> array;
int count = 0;
}
for(int i = 0;i <array.size()/2; i++){
if(array[i]!= array[array.size()-i-1])
return false;
}
return true;

}
};``````

Thought 2:

Use the fast and slow pointers to find the middle, reverse the second half and start comparing from the middle.

``````class Solution {
public:
while(fast){//find mid node
slow = slow->next;
fast = fast->next? fast->next->next:fast->next;
}
while(slow){//reverse
ListNode* temp = slow->next;
slow->next = prev;
prev = slow;
slow = temp;
}
return false;
}
prev = prev->next;
}
return true;
}
};``````

#### Interview question 02.05. List summation

Medium difficulty 23

Given two integers represented by a linked list, each node contains a digit.

These digits are stored in reverse, that is, the digits are arranged at the head of the linked list.

Write a function to sum the two integers and return the result in a linked list.

Example:

``````Input:(7 -> 1 -> 6) +(5 -> 9 -> 2), which is 617 + 295
Output:2 -> 1 -> 9, which is 912``````

Example:

``````Input:(6 -> 1 -> 7) +(2 -> 9 -> 5), which is 617 + 295
Output:9 -> 1 -> 2, which is 912``````

Thinking:

The idea of this question is very clear:the merge of the linked list + the carry problem.(The merger of linked lists will be specifically discussed in the topic of linked lists)

``````class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *sum = l1;
while(l1->next && l2->next)
{
l1->val += l2->val;
l1 = l1->next;
l2 = l2->next;
}
l1->val += l2->val;
if(!l1->next)
{
l1->next = l2->next;
}
l1 = sum;
while(l1->next)
{
if(l1->val >= 10)
{
l1->val -= 10;
l1 = l1->next;
l1->val++;
}
else
{
l1 = l1->next;
}
}
if(l1->val >= 10)
{
l1->val -= 10;
l1->next = new ListNode(1);
return sum;
}
else
{
return sum;
}
}
};``````

Related Posts