The second phase of algorithm training-linked list

Posted Jun 27, 20204 min read

Reverse linked list

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;

/**
 * Definition for singly-linked list.
 * struct ListNode {
 * int val;
 * ListNode *next;
 * ListNode(int x):val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL) return NULL;
        if(head->next == NULL) return head;
        stack<ListNode*> stack_listnode;
        while(head != NULL) {
            stack_listnode.push(head);
            head = head->next;
        }
        ListNode* q = stack_listnode.top();
        ListNode* qHead = q;
        stack_listnode.pop();
        while(stack_listnode.size() != 0) {
            q->next = stack_listnode.top();
            stack_listnode.pop();
            q = q->next;
        }
        q->next = NULL;
        return qHead;
    }
};

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* reverseList(ListNode* head) {
        ListNode *p1,*p2,*p3;
        p1 = NULL;
        p2 = head;
        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.

/**
 * Definition for singly-linked list.
 * 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

234. Palindrome Linked List

Simple difficulty 533

Please determine whether a linked list is a palindrome linked list.

Example 1:

Input:1->2
Output:false

Example 2:

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

Advanced:
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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 * int val;
 * ListNode *next;
 * ListNode(int x):val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(head == NULL) return true;
        if(head->next == NULL) return true;
        vector<int> array;
        int count = 0;
        while(head != NULL){
            array.push_back(head->val);
            head = head->next;
        }
        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:
    bool isPalindrome(ListNode* head) {//O(n), O(1)
        ListNode* slow = head, *fast = head, *prev = nullptr;
        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;
        }
        while(head && prev){//check
            if(head->val != prev->val){
                return false;
            }
            head = head->next;
            prev = prev->next;
        }
        return true;
    }
};

Linked list summation

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

Advanced:Assuming these digits are stored positively, please do it again.

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