Li Kou, niuke.com - > linked list related topics (Article 1) (C language)

Catalog

1.LeetCode203. Remove linked list elements

Method 1 ： Double pointer

Method 2 ： Create a new linked list

Method 3 ： recursive

2.LeetCode206. Reverse a linked list

Method 1 ： Create a new linked list

Method 2 ： Three pointers

Method 3 ： recursive

3.LeetCode876. The middle node of a linked list

solution ： Speed pointer

4. Cattle from JZ22： Last in the list k Nodes

  solution ： Speed pointer

 5.LeetCode21. Merge two ordered lists

Method 1 ： Create a new linked list

Method 2 ： recursive

---

1.LeetCode203. Remove linked list elements

Method 1 ： Double pointer

Set two pointers prev and cur, Give Way cur Point to the head ,prev Pointing empty , Delete the nodes in sequence, and the value is val The node of

    // Method 1 ： Double pointer 
    struct ListNode*cur=head,*prev=NULL;
    while(cur){
        if(cur->val==val){
            if(cur==head){
                head=cur->next;
                free(cur);
                cur=head;
            }else{
                 prev->next=cur->next;
             free(cur);
             cur=prev->next;
            }
            
        }else{
            prev=cur;
            cur=cur->next;
        }
    }
    return head;

Method 2 ： Create a new linked list

Traversing the linked list , Let's not val The end of the node of the value is inserted into the new linked list

// Method 2 ： Create a new linked list 
    struct ListNode*newhead=(struct ListNode*)malloc(sizeof(struct ListNode)); 
    newhead->next=NULL;
    struct ListNode*tail=newhead;
    struct ListNode*cur=head;
    while(cur){
        if(cur->val==val){
            struct ListNode*next=cur->next;
            free(cur);
            cur=next;
        }else{
          tail->next=cur;
          tail=tail->next;
          cur=cur->next;
        }
    }
    tail->next=NULL;
    return newhead->next;

Method 3 ： recursive

1. Judge the head node , If the conditions are met, delete

2. Treat the head node as a linked list 2

3. Recursively delete linked list 2（ recursive 1-3 Step ）

4. Return to header node

// Method 3 ： recursive 
    if(head==NULL)return NULL;
    while(head&&head->val==val){
        struct ListNode*next=head->next;
        free(head);
        head=next;
    }
    if(head)head->next=removeElements(head->next,val);
    return head;

2.LeetCode206. Reverse a linked list

Method 1 ： Create a new linked list

Create a pointer variable newlist Let it point to the head pointer head, Create pointer cur Points to the next node of the head node , Let the head pointer point to NULL, use next Pointer to cur The next node of a node . Pictured ：

Insert the head of the right linked list into the left linked list in turn according to the figure , Finally back to *newlist or head that will do .

// Method 1 ： Create a new linked list 
   if(head==NULL)return NULL;
   struct ListNode**newlist=&head;
   struct ListNode*cur=head->next; 
     head->next=NULL;
   while(cur){
       struct ListNode*next=cur->next;
       cur->next=(*newlist); 
       *newlist=cur;
       cur=next;
   }

   return (*newlist);

Method 2 ： Three pointers

Create three points to the current node 、 Precursor node 、 And the pointer variable of the next node , The precursor node refers to the head node at the beginning , Let the current node point to the precursor node , Then let the three pointers go back , Until the current node points to null .

// Method 3   Three pointers 
struct ListNode* reverseList(struct ListNode* head){
    if(head==NULL||head->next==NULL)return head;
    struct ListNode*pre=NULL,*cur=head,*next=head->next;
    while(cur){
        cur->next=pre;
        pre=cur;
        cur=next;
        if(next)
        next=next->next;
    }
return pre;
}

Method 3 ： recursive

1. Give Way tail The pointer points to the next node of the header node .p For tail The address of the head node after the chain list at the beginning of the next node is reversed , It is also the address after the reverse of the linked list .

2. Give Way head Pointer to null node

3. Give Way tail Point to the head node

4. return p

//2. Recursive implementation 
if(head==NULL||head->next==NULL)return head;
struct ListNode*tail=head->next,*p=reverseList(tail);
head->next=NULL;
tail->next=head;
return p;

3.LeetCode876. The middle node of a linked list

solution ： Speed pointer

Let's go two steps , Slow pointer one step , Finish the pointer , The slow pointer points to the intermediate node .

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

4. Cattle from JZ22： Last in the list k Nodes

  solution ： Speed pointer

Let the quick pointer go first k Step , Then the two pointers go together , Finish the pointer , The slow pointer points to the penultimate in the list k Nodes .

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

 5.LeetCode21. Merge two ordered lists

 

Method 1 ： Create a new linked list

Give Way cur1,cur2 The pointer points to the head node of the two linked lists , take cur The end of the node with a small value of the node is inserted into the new linked list , And let cur The pointer goes back , Until there is one cur The pointer points to null .

// Method 1 ： Create a new linked list 
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
if(list1==NULL||list2==NULL)return list1==NULL?list2:list1;
    struct ListNode*cur1=list1,*cur2=list2;
    struct ListNode*newlist;
    if(cur1->val<cur2->val){
        newlist=cur1;
        cur1=cur1->next;
    }
    else{
     newlist=cur2;
    cur2=cur2->next;    
    }
    struct ListNode*tail=newlist;
    while(cur1&&cur2){
        if(cur1->val<cur2->val){
          tail->next=cur1;
          cur1=cur1->next;
          tail=tail->next;
        }else{
            tail->next=cur2;
            cur2=cur2->next;
            tail=tail->next;
        }
    }
   if(!cur1)
       tail->next=cur2;
   else
       tail->next=cur1;
    return newlist;
}

Method 2 ： recursive

1. Judge list1 and list2 The value size relationship of nodes , if list1 The value of is small , Give Way list1 The node is the head node .（ if list2 The smaller value of list2 Make the head node , The following steps are reversed ）

2. Merge to list1->next and list2 Make two linked lists of head nodes respectively （ Recursive implementation ）, Return the head node of the merged linked list , Give Way list1 The next node of is this node .

3. return list1 As head node .

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
   if(list1==NULL||list2==NULL)return list1==NULL?list2:list1;
   if(list1->val<list2->val){
       list1->next=mergeTwoLists(list1->next,list2);
       return list1;
   } 
   else {
       list2->next=mergeTwoLists(list1,list2->next);
       return list2;
   }
}