[Data Structure and Algorithm] Hand torn linked list OJ question

Article directory

remove [list] element

Give you the head node of a linked list headand an integer val, please delete all Node.val == valthe , and return the new head node

Idea 1 : A more common way to find differences while traversing. We can define two pointers, one pointing to the head node and one set to NULL. When encountering the same value, skip directly. point to the next bit. At the same time, we have to pay attention to the problem of head deletion, because the function given in the title has the head node head.

struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode*cur = head;
    struct ListNode*prev = NULL;
    while(cur)
    {
        if(cur->val == val)
        {
            if(cur==head)
            {
                head = head->next;
                free(cur);
                cur = head;
            }
            else
            {
                prev->next = cur->next;
                free(cur);
                cur = prev->next;
            }
        }
        else
        {
            prev = cur;
            cur = cur->next;
        }
    }
    return head;
}

Idea 2 : Give a new linked list, not the end of the val node can be inserted into the new linked list. The last node is set to NULL. At the same time, we still need to pay attention to the problem of the head node

struct ListNode* removeElements(struct ListNode* head, int val){ 
    struct ListNode*cur = head;
    struct ListNode*newhead= NULL,*tail =NULL;
    while(cur)
    {
        if(cur->val!=val)
        {
            if(tail==NULL)
            {
                newhead = tail = cur;
            }
            else
            {
                tail->next = cur;
                tail = tail->next;
            }
            cur = cur->next;
        }
        else
        {
            struct ListNode*del = cur;
            cur = cur->next;
            free(del);
        }
    }
    if(tail)
    tail->next = NULL;
    return newhead;
}

It is not difficult for us to find that if there is no head node, we have to pay attention, so we can give a singly linked list of the head node to implement :

struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode*cur = head;
    struct ListNode*guard = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode*tail = guard;
    while(cur)
    {
        if(cur->val != val)
        {
            tail->next = cur;
            tail = tail->next;
            cur = cur->next;
        }
        else
        {
            struct ListNode*del = cur;
            cur = cur->next;
            free(del);
        }
    }
    if(tail)
          tail->next = NULL;
    head = guard->next;
    free(guard);
    return head;
}

After we have the head node, we don’t need to think about deleting the first element.

Merge two sorted linked lists

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

Idea: It is relatively simple, create a linked list with a head node, compare the size of the data, and insert the tail after the new linked list.

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
     struct ListNode*guard = (struct ListNode*)malloc(sizeof(struct ListNode));
    guard->next = NULL;
    struct ListNode*cur1 = list1;
    struct ListNode*cur2 = list2;
    struct ListNode*tail = guard;
    while(cur1&&cur2)
    {
        if(cur1->val<cur2->val)
        {
            tail->next = cur1;
            cur1 = cur1->next; 
        }
        else
        {
            tail->next = cur2;
            cur2 = cur2->next;
        }
        tail = tail->next;
    }
    if(cur1)
    {
        tail->next = cur1;
    }
    if(cur2)
    {
        tail->next = cur2;
    }
    struct ListNode*head = guard->next;
    free(guard);
    return head;
}

reverse linked list

Given the head node of the singly linked list head, please reverse the linked list and return the reversed linked list.

Idea 1: Take the node and insert it into a new node

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

Idea 2: Flip the direction of the pointer directly to flip the linked list

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode*cur = head;
    struct ListNode*prev = NULL;
    while(cur)
    {
        struct ListNode*next = cur->next;
        cur->next = prev;

        prev = cur;
        cur = next;
    }
    return prev;
}

middle node of linked list

Given heada , return the middle node of the linked list.

If there are two intermediate nodes, return the second intermediate node.

Idea: You can traverse it once to find the length divided by 2. However, we can use another method to just traverse the linked list once, using the fast and slow pointers. The slow pointer takes one step at a time, and the fast pointer takes two steps at a time. We need to distinguish whether it is an odd number of nodes or an even number of nodes.

For odd numbers: fast to the end, and slow to just the middle node

For even numbers: fast goes to empty, while slow just goes to the middle node.

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode*fast = head;
    struct ListNode*slow = head;
    while(fast&&fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

The k-th node from the bottom in the linked list

Input a linked list and output the k-th node from the bottom of the linked list.

Idea: still use the fast and slow pointer approach. Slow takes one step at a time, while fast we let it take K steps first . Then go at the same time.

struct ListNode* FindKthToTail (struct ListNode* pListHead, int k )  {
     // write code here 
    struct  ListNode * slow = pListHead ,* fast = pListHead ; 
    while (k--){
         //k is greater than the length of the linked list 
        if (fast == NULL )
             return  NULL ;
        fast = fast->next;
    }
    while(fast){
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

fast What if you take the K-1 step first? What about changing K- to –K? We need to modify some of the conditions inside (we focus on analyzing some boundary problems):

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
    struct ListNode*slow = pListHead,*fast = pListHead;
    while(fast&&--k){
        fast = fast->next;
    }
      if(fast == NULL)
            return NULL;

    while(fast->next){
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

Linked list split

There is a head pointer ListNode pHead* of a linked list , given a certain value x, write a piece of code to arrange all nodes less than x before the rest of the nodes, and the original data order cannot be changed, and return the head pointer of the rearranged linked list.

Idea: We give two new linked lists with head nodes, the value less than X is placed in the first linked list, the value greater than X is placed in the second linked list, and the last two new linked lists can be connected. At the same time, we need to note that if the linked list is empty, we can draw a picture:

public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        ListNode*lessguard = (ListNode*)malloc(sizeof(ListNode));
        lessguard->next = NULL;
        ListNode*lesstail = lessguard;
        ListNode*greaterguard = (ListNode*)malloc(sizeof(ListNode));
        greaterguard->next =NULL;
        ListNode*greatertail = greaterguard;
        ListNode*cur = pHead;
        while(cur)
        {
            if(cur->val<x)
            {
                lesstail->next = cur;
                lesstail = lesstail->next;
            }
            else
            {
                greatertail->next = cur;
                greatertail = greatertail->next;
            }
            cur = cur->next;
        }
        lesstail->next = greaterguard->next;
        greatertail->next = NULL;
        pHead = lessguard->next;
        free(lessguard);
        free(greaterguard);
        return pHead;
    }
};

Palindromic linked list

Given the head node of a singly linked list head, please judge whether the linked list is a palindrome linked list. If yes, return true; otherwise, return false.

Idea: Find the middle position, invert the second half, and compare, and it will be NULL at the end. This is actually a collection of finding the intermediate node of the linked list and reversing the linked list :

class Solution {
public:
      struct ListNode* reverseList(struct ListNode* head) {
        struct ListNode* newhead = NULL;
        struct ListNode* cur = head;
        while (cur)
        {
            struct ListNode* next = cur->next;
            cur->next = newhead;
            newhead = add;
            cur = next;
        }
        return newhead;
    }
     struct ListNode* middleNode(struct ListNode* head) {
         struct ListNode*slow = head;
         struct ListNode*fast = head;
         while(fast&&fast->next)
         {
             slow = slow->next;
             fast = fast->next->next;
         }
         return slow;

}
    bool  isPalindrome (ListNode* head)  {
         // write code here 
        struct  ListNode * mid = middleNode ( head ); 
        struct  ListNode * ret = reverseList ( mid ); 
        //1 2 3 2 1 
        // reverse middle first 
        // 1 2 1 2 3 
        while (head && ret)
        {
            if (head->val == ret->val)
            {
                head = head->next;
                ret = ret->next;
            }
            else
            {
                return  false ;
            }
        }
        return true;
    }
};

Another solution: create a linked list to store the inversion result of the original linked list, and then compare it with the original linked list one by one to determine whether it is a palindrome :

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        // write code here
        struct ListNode*cur = head;
        struct ListNode*newhead = NULL;
        struct ListNode*next = NULL;
        while(cur)
        {
            newhead = (struct ListNode*)malloc(sizeof(struct ListNode));
            newhead->val = cur->val;
            newhead->next = next;
            next = newhead;
            cur = cur->next;
        }
        while(head)
        {
            if(newhead->val!=head->val)
            {
                return  false ;
            }
            else
            {
                newhead =newhead->next;
                head = head->next;
            }
        }
        return true;

    }
};

Intersecting linked list

Given the head nodes headA and headB of two singly linked lists, please find and return the starting node where the two singly linked lists intersect. Returns null if the two linked lists do not have intersecting nodes.

The illustration shows that the two linked lists intersect at node c1:

The title data guarantees that there are no cycles in the entire chain structure.

Idea: First of all, it is necessary to determine whether there is any intersection, whether the addresses of the end nodes are the same

Find the intersection point – find the length, which is the length of LenA and LenB. The long linked list takes the difference step first, and then walks at the same time. The first equality is the required intersection, because we have already judged whether it intersects.

struct ListNode * getIntersectionNode (struct ListNode *headA, struct ListNode *headB)  {
     struct  ListNode * curA = headA ,* curB = headB ; 
    int LenA = 0 ;
    int LenB = 0 ;
    while (curA)
    {
        curA = curA->next;
        LenA++;
    }
    while(curB)
    {
        curB = curB->next;
        LenB++;
    }
    if(curA!=curB)
    {
        return NULL;
    }
   struct ListNode*longList = headA,*shortList = headB;
   if(LenA<LenB)
   {
       longList = headB;
       shortList = headA;
   }
   int gap = abs(LenA-LenB);
   while(gap--)
   {
       longList = longList->next;
   }
   while(longList != shortList)
   {
       longList = longList->next;
       shortList = shortList->next;
   }
   return longList;
}

circular linked list

Give you the head node of a linked list, and determine whether there is a cycle in the linked list.

If there is a node in the linked list that can be reached again by continuously tracing the next pointer, there is a cycle in the linked list. To represent a cycle in a given linked list, the evaluation system internally uses the integer pos to represent the position in the linked list where the tail of the linked list is connected (index starts from 0). Note: pos is not passed as a parameter. Just to identify what the linked list actually is.

Returns true if there is a cycle in the linked list. Otherwise, return false.

Idea: A linked list with a ring cannot be traversed. . . We can use fast and slow pointers to solve this problem. Fast and slow pointers, that is, slow pointers take one step at a time, fast pointers take two steps at a time, and the two pointers start to run from the actual position of the linked list. If the linked watch has a ring, it will definitely meet in the ring. Otherwise the fast pointer goes to the end of the linked list first :

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

}

extension problem

Why does the fast pointer take two steps at a time, and the slow pointer can catch up with one step, will I miss it?

  • Slow take one step at a time, fast take three steps at a time❓

  • Slow takes one step at a time, fast takes X steps at a time❓

  • slow takes Y steps at a time, fast takes X steps at a time❓

The latter problem is also a similar solution. What about taking one step at a time for slow and X steps at a time for fast? Each time the distance is reduced by X-1

And what about slow taking Y steps at a time and fast taking X steps at a time? Each time the distance is reduced by XY

This is actually a matter of relative distance reduction.

Ring List II 😱

Given the head node head of a linked list, return the first node that the linked list starts to enter the ring. Returns null if the linked list has no cycle.

If there is a node in the linked list that can be reached again by continuously tracing the next pointer, there is a cycle in the linked list. To represent a cycle in a given linked list, the evaluation system internally uses the integer pos to represent the position in the linked list where the tail of the linked list is connected (index starts from 0). If pos is -1, there are no cycles in the list. Note: pos is not passed as a parameter, just to identify the actual situation of the linked list.

Modifying the linked list is not allowed.

Idea 1: Here is a conclusion (the first node in the ring):

Let a pointer start traversing the linked list from the starting position of the linked list, and at the same time let a pointer start to run around the circle from the position of the meeting point, both pointers take one step each time, and will eventually meet at the position of the entry point .

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode*slow = head,*fast = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
        {
            struct ListNode*meet = slow;
            while(head!=meet)
            {
                head = head->next;
                meet = meet->next;
            }
            return meet;
        }
    }
    return NULL;
}

Idea 2: Convert into an intersecting linked list. After disconnecting from the meeting point, as a linked list, the other linked list starts from the beginning. The first node of the linked list to enter the ring is equivalent to the intersection of these two linked lists, and finding the intersection of the linked lists is The above topics intersect the linked list.

struct ListNode * getIntersectionNode (struct ListNode *headA, struct ListNode *headB)
  {
      struct  ListNode * curA = headA ,* curB = headB ; 
     int LenA = 0 , LenB = 0 ;
     while (curA)
     {
         curA = curA->next;
         LenA++;
     } 
     while(curB)
     {
         curB = curB->next;
         LenB++;
     }
     if(curA != curB)
     {
         return NULL ;
     }
     struct ListNode*longlist = headA,*shortlist = headB;
     if(LenA<LenB)
     {
         longlist = headB;
         shortlist = headA;
     }
     int gap = abs(LenA-LenB);
     while(gap--)
     {
         longlist = longlist->next;
     }
     while(longlist!=shortlist)
     {
         longlist = longlist->next;
         shortlist = shortlist->next;
     }
     return longlist;
 }
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode*slow = head,*fast = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
        {
            //find the meeting point 
            struct  ListNode * meet = slow ; 
            struct  ListNode * next = meet -> next ; 
            // disconnect 
            meet->next = NULL ;
            struct  ListNode * enterNode = getIntersectionNode ( head , next ); 
           // restore the original linked list
           meet->next = next;
           return enterNode;
        }
    }
    return NULL;
}

Copy linked list with random pointer 😰

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

Constructs a deep copy of this linked list. A deep copy should consist of exactly n new nodes, where 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 copied linked list, so that these pointers in the original linked list and the copied linked list can represent the same linked list state. None of the pointers in the copied linked list should point to the nodes 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 replication linked list also have x.random –> y .

Returns the head node of the replicated linked list.

A linked list in input/output is represented by a linked list consisting of n nodes. Each node is represented by a [val, random_index]:

val: An integer representing Node.val.
random_index: The index of the node pointed to by the random pointer (ranging from 0 to n-1); null if it does not point to any node.
Your code only accepts the head node of the original linked list as an incoming parameter.

This question is more difficult. If we replicate each node, the randomness of this problem is more difficult for us to deal with:

struct Node* copyRandomList(struct Node* head) {
    struct Node* cur = head;
    struct Node*copy = NULL;
    struct Node*next = NULL;
    while(cur)
    {
        //assign link
        next = cur->next;
        copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;

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

    //Update the random of copy
    cur = head;
    while(cur)
    {
        copy = cur->next;
        if(cur->random == NULL)
        {
            copy->random = NULL;
        }
        else
        {
            copy->random = cur->random->next;
        }
        //iterate
        cur = cur->next->next;
    }
    //copy nodes are unlinked and linked together to restore the original linked list 
    struct Node*copyHead = NULL ,*copyTail = NULL ;
    cur = head;
    while(cur)
    {
        copy = cur->next;
        next = copy->next;

        / / Take the node tail insertion 
        if (copyTail == NULL )
        {
            copyHead = copyTail = copy;
        }
        else
        {
            copyTail->next = copy;
            copyTail = copyTail->next;
        }
        // restore the original list
        cur->next = next;

        cur = next;
    }
    return copyHead;
}

Summarize

  • Through the above linked list OJ questions, we have a deeper understanding of linked lists, and at the same time, we have learned some problem-solving methods. At the same time, for the questions, the first thing we need to do is to understand the meaning of the questions, and then we need to draw more pictures. It is convenient for us to better deal with some details.

  • Of course, there are still many OJ questions for linked lists. The questions here are just the representative of linked list questions. It does not mean that this is the question of all linked lists.

Leave a Comment

Your email address will not be published. Required fields are marked *