[C language brush questions] explanation of linked list application

Catalog

NC25  Delete duplicate elements in the ordered linked list -I

describe

Method 1 ： Traverse delete （ Recommended ）

Method 2 ： Recursive solution

Reverse a linked list

describe

solution ： iteration

---

Recommend an artifact to everyone Cattle from The following questions and methods are available to Niuke , And enterprise interview high-frequency questions

 

NC25  Delete duplicate elements in the ordered linked list -I

describe

Delete the duplicate elements in the given linked list （ The elements in the linked list are ordered from small to large ）, Make all elements in the linked list appear only once
for example ：
The list given is 1→1→2, return 1→2.
The list given is 1→1→2→3→3, return 1→2→3.

Data range ： The length of the linked list meets 0≤n≤100, The value of any node in the linked list satisfies val∣≤100

Advanced ： Spatial complexity  O(1)O(1), Time complexity  O(n)O(n)

  We can get such information in the title :

• Given a small to large ordered list
• Delete the repeated elements in the linked list , Each value leaves only one node

Method 1 ： Traverse delete （ Recommended ）

Ideas ：

Since only one element is left in succession , Which one is the best for us to stay ？ Of course, it is the first element encountered ！

if(cur->val==cut->next->val)
    cur->var=cur->next->next;

Because the first element is directly connected with the previous linked list node , Don't worry about the front , It only needs Skip repeat after The elements of , Just connect the first non repeating element , It is always more convenient to connect the following elements in the linked list than the previous elements , Because you cannot access in reverse order .

specific working means ：

• step 1： Judge whether the linked list is empty , Empty linked list is returned directly without processing .
• step 2： Use a pointer to traverse the linked list , If the current node of the pointer has the same value as the next node , Let's skip the next node , The current node is directly connected to the next node .
• step 3： If the value of the current node is different from that of the next node , Continue to traverse back .
• step 4： Two node values are used each time during the cycle , To check whether two consecutive nodes are empty .

 

Moving pictures show ：

  Core code

struct ListNode* deleteDuplicates(struct ListNode* head ) {
    if(head == NULL || head->next == NULL) return head;
    struct ListNode *p=head,*pn = head->next;
    while(p){
        if(p->val == pn->val){
            while(pn&&pn->val == p->val) // Judge 
            pn = pn->next;
            p->next = pn;// Delete 
        }
        p = p->next;
        
    }
    return head;
    // write code here
}

 

Complexity analysis ：

• Time complexity ：O(n)O(n)O(n), among nnn Is the length of the list , Traverse the list once
• Spatial complexity ：O(1)O(1)O(1), Constant level pointer variables use , No additional auxiliary space is used

Method 2 ： Recursive solution

The core idea ：
         Use the idea of recursion to solve . Each recursion requires comparing and deleting duplicate elements . The idea of this time is very similar to recursive inverse linked list , The only difference is the processing logic . The processing logic of deleting duplicate linked lists is to delete the current node every time （ If the current node is the same as the next node ）

Core code ：

ListNode* deleteDuplicates(ListNode* head) {
    if (head == nullptr || head->next == nullptr)    // When a node does not exist or there is only one node , Recursion ends 
        return head;
    head->next = deleteDuplicates(head->next);      // Recursive body , Each recursion starts at the next node 
    if (head->val == head->next->val)     // Compare whether the values of the current element and the next element are equal , If equal, delete the current node directly 
        head = head->next;            //head The pointer points to the next node , Indicates that the current node is missing , It no longer belongs to this linked list 
    return head;                // Return the result of this recursion 
}

Complexity analysis ：
         recursive n Time , So the time complexity is zero O(N). Each recursion requires an additional variable to be saved , So the space complexity is zero O(N), Time complexity O(n)
 

Reverse a linked list

describe

Given the head node of a single linked list pHead( The header node has a value , For example, in the figure below , its val yes 1), The length is n, After reversing the linked list , Return the header of the new linked list .

Data range ：0≤n≤1000

requirement ： Spatial complexity  O(1)O(1) , Time complexity  O(n)O(n) .

For example, when entering a linked list {1,2,3} when ,

After reversal , The original linked list becomes {3,2,1}, So the corresponding output is {3,2,1}.

The above conversion process is shown in the figure below ：

 

 

solution ： iteration

• When traversing a linked list , Set the... Of the current node next The pointer changes to point to the previous node . Because the node does not refer to its previous node , So you have to store its previous node in advance . Before changing the reference , You also need to store the latter node . Finally, the new header reference is returned .
• The illustration ：

 

Complexity analysis ：

Time complexity ：O(N), among N It's the length of the list . You need to traverse the linked list once .

Spatial complexity ：O(1), Constant space complexity

Code display :

```/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C Language declaration defines global variables. Please add static, Prevent duplicate definitions 
 */

struct ListNode* ReverseList(struct ListNode* pHead ) {
    if(!pHead)return NULL;
    if(pHead->next==NULL)return pHead;
    struct ListNode *p,*t;
    t=pHead->next;
    p=pHead;p->next=NULL;
    while(t){
        p=t;
        t=t->next;
        p->next=pHead;
        pHead=p;
    }
    return p;
}

Click the link on the right Cattle from - Looking for work artifact | Written examination question bank | The interview experience | Internship recruitment push , One stop job search _ Cattle from