Linked list operation can never change without its roots

1. Basic introduction to linked list

A list is a kind of The physical storage structure is discontinuous 、 Out of order Storage structure , Data elements Logical order It is through... In the linked list Pointer link Sequential implementation of . In practice, the structure of linked list is very diverse , In practice, two structures are most commonly used ：

1. Headless unidirectional acyclic list ： Simple structure , Generally, it is not used to store data alone . In fact, it is more as a substructure of other data structures , Such as hash bucket 、 Adjacency table of graph and so on .
2. Take the lead in two-way circular list ： The most complex structure , It's usually used to store data separately . Although the structure is complex , But there are many advantages in operation .

2. Headless one-way acyclic linked list

This is a commonly used linked list ,oj Often used in questions , Interview is also commonly used
Realize the complete program of linked list

3. Take the lead in two-way circular list

The advantage of taking the lead in two-way circular linked list is reflected in its basic operation ：
Realize a leading two-way circular linked list with functions of addition, deletion and modification

4. Linked list classic topic analysis

① Remove linked list elements

Topic link

Give you a list of the head node head And an integer val , Please delete all the contents in the linked list Node.val == val The node of , And back to New head node .
Answer and analysis

② Reverse a linked list

Topic link

Here's the head node of the list head , Please reverse the list , And return the inverted linked list

Method 1 ：
Define three pointers n1 n2 n3,n1 Record the last node location ,n2 Is the current location ,n3 Is the next node location , When modifying, the current position points to the previous position , then n1,n2,n3 All backward . Pictured ：

The procedure is as follows ：

struct ListNode* reverseList(struct ListNode* head){
    
        if (!head)
		return head;
	struct ListNode* n1 =NULL;// Record the last node location 
	struct ListNode* n2 = head;// The current position 
	struct ListNode* n3 = head->next;// Record the next position 
	while (n2)
	{
    
		n2->next=n1;
        n1=n2;
        n2=n3;
		if(n3)
        n3=n3->next;
	}
    return n1;
}

Method 2 ：
Traverse the nodes and insert them in turn , Make the initial tail node into a new head node

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=cur;
          cur=next;
      }
      return newhead;
}

③ The middle node of a list

Topic link

Given a header node as head The non empty single chain table of , Returns the middle node of the linked list .
If there are two intermediate nodes , Then return to the second intermediate node .

Ideas ： Fast and slow pointer method , Slow pointer one step , Let's go two steps .

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

④ Last in the list k Nodes

Topic link

Ideas ：
The fast and slow pointer method is more convenient , Let's go first k Step , Then the hands go fast and slow at the same time , Pay attention to special circumstances .

The procedure is as follows ：

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    
     if(!pListHead)
        return NULL;
     struct ListNode* low=pListHead;
     struct ListNode* fast=pListHead;
     while(k--)
     {
    
        if(fast==NULL)
            return NULL;
        fast=fast->next;
     }
     while(fast)
     {
    
        low=low->next;
        fast=fast->next;
     }
     return low;
}

⑤ Integrate two ordered linked lists

Topic link

Ideas ： Create new header , Compare the current node values of the two linked lists , Small ones are inserted at the end of the new linked list , Connect all the rest

The procedure is as follows ：

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    
          if(!l1)
             return l2;
          if(!l2)
             return l1;
          struct ListNode* newhead=NULL;
          struct ListNode* tail=NULL;
          struct ListNode* cur1=l1;
          struct ListNode* cur2=l2;
          if(cur1->val<cur2->val)
          {
    
              newhead=l1;
              tail=l1;
              cur1=cur1->next;
          }
          else
          {
    
              newhead=l2;
              tail=l2;
              cur2=cur2->next;
          }
        
          while(cur1&&cur2)
          {
    
              if(cur1->val<cur2->val)
              {
    
                tail->next=cur1;
                tail=cur1;
                cur1=cur1->next;
              }
              else
              {
    
                tail->next=cur2;
                tail=cur2;
                cur2=cur2->next;
              }
          }
          if(cur1==NULL)
            tail->next=cur2;
          else
            tail->next=cur1;

         return newhead;
}

Tips ：
The code for creating a new header is a little long , Sure Open up a sentinel node , Then start comparing directly , Finally, return the required pointer , Release sentinel node

⑥ Sort some nodes of the linked list

Topic link

The head pointer of an existing linked list ListNode* pHead, Give a certain value x, Write a piece of code that will all be less than x The nodes of are arranged before the other nodes , And the original data order cannot be changed , Returns the head pointer of the rearranged linked list

Ideas ： Open up two new heads , Less than x Link together , The rest are linked together , Then the two chains are linked together

The procedure is as follows ：

class Partition {
    
public:
    ListNode* partition(ListNode* pHead, int x) {
    
         struct ListNode* lessHead,*lessTail,*greaterHead,*greaterTail;
         lessHead=lessTail=(struct ListNode*)malloc(sizeof(struct ListNode));
         greaterHead=greaterTail=(struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* cur=pHead;
        while(cur)
        {
    
            if(cur->val<x)
            {
    
                lessTail->next=cur;
                lessTail=cur;
            }
            else
            {
    
                greaterTail->next=cur;
                greaterTail=cur;
            }
            cur=cur->next;
        }
        
        greaterTail->next=NULL;
        
        lessTail->next=greaterHead->next;
        struct ListNode* p=lessHead->next;
        free(lessHead);
        free(greaterHead);
        return p;
    }
};

⑦ Palindrome structure of linked list

Topic link

For a linked list , Please design a time complexity of O(n), The extra space complexity is O(1) The algorithm of , Judge whether it is palindrome structure .
Given the head pointer of a linked list A, Please return one bool value , Represents whether it is palindrome structure . Ensure that the length of the linked list is less than or equal to 900.

Ideas ： Find the middle node of the list , Reverse the last half of the chain , Traversal comparison .（ May refer to ②,③）

class PalindromeList {
    
public:
// Find the middle node 
struct ListNode* middleNode(struct ListNode* head)
{
    
    struct ListNode* fast=head;
    struct ListNode* low=head;
    while(fast&&fast->next)
    {
    
        low=low->next;
        fast=fast->next->next;
    }
     return low;
}
// Reverse order of linked list 
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=cur;
          cur=next;
      }
      return newhead;
}
 
bool chkPalindrome(ListNode* A) 
{
    
       struct ListNode * mid = middleNode(A);
       struct ListNode * rhead = reverseList(mid);// The new head after the reverse order is rhead
       
       struct ListNode *head = A;
       while(head&&rhead)
       {
    
           if(head->val!=rhead->val)
               return false;
           
           head=head->next;
           rhead=rhead->next;
       }
       return true;
}
};

⑧ Public node of linked list

Topic link

Here are two head nodes of the single linked list headA and headB , Please find out and return the starting node where two single linked lists intersect . If there is no intersection between two linked lists , return null

Ideas ： First judge whether the linked list intersects , The last node of the intersecting linked list should be the same .
If it intersects , Calculate the length of the two linked lists , Define two pointers to two linked lists , Long list first take two steps of the length difference of the linked list , Then both hands go at the same time , When you go to a position in front of the public node ,next The value of is the same , find .

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    
   // Determine the length of the two linked lists 
    struct ListNode * curA = headA;
    struct ListNode * curB = headB;
    int lenA = 0, lenB = 0;
    while(curA)
    {
    
        lenA++;
        curA=curA->next;
    }
    while(curB)
    {
    
        lenB++;
        curB=curB->next;
    }
   // hypothesis A Longer , If not , In exchange 
    struct ListNode * longList =headA;
    struct ListNode * shortList =headB;
    if(lenA<lenB)
    {
    
        longList=headB;
        shortList=headA;
    }
    // Long chain takes the first step 
    int gap = abs(lenA-lenB);
    while(gap--)
    {
    
        longList = longList->next;
    }
   // Go at the same time , Judge whether there is intersection 
    while(longList&&shortList)
    {
    
        if(longList == shortList)
        {
    
            return longList;
        }
        shortList = shortList->next;
        longList = longList->next;
    }

    return NULL;
}

⑨ Linked list

a. Determine if the list has links

Topic link

Given a linked list , Judge whether there are links in the list

Ideas ： The speed pointer walks from the beginning at the same time , Slow pointer one step , Let's go two steps , If there are rings , The fast and slow pointers will meet

The procedure is as follows ：

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

b. Return the ring entry position of the linked list with links

Topic link

Given a linked list , Return to the first node of the link where the list begins to enter . If the list has no links , Then return to null.

Ideas ：
There is a conclusion ： use a Method to determine whether the linked list has a ring , If there is , You can find where the fast and slow pointers meet , Make a pointer walk step by step from where it meets , Make the other pointer walk step by step at the same time , They will eventually meet at the entrance
Proof process ：
（ There are many details worth thinking about in this process ）

The procedure is as follows ：

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

⑩ Each node contains a linked list of random pointers

Topic link

Give you a length of n The linked list of , Each node contains an additional random pointer random , The pointer can point to any node or null node in the list .
To construct this linked list Deep copy . The deep copy should be made exactly by n individual new Node composition , The value of each new node is set to the value of its corresponding original node . New nodes next Pointers and random The pointer in the list should also point to the new node , And make these pointers in the original linked list and the copied linked list represent the same linked list state . The pointer in the copy linked list should not point to the node in the original linked list

Ideas ：
think first of , Traversal replication , But the node pointed to by the random pointer of the current position may not have been created
One method ：
Insert a new node after each node , Then assign a value to the random pointer of the new node , Finally, link all the new nodes just inserted and copy successfully .
The basis of random pointer assignment ： Each newly inserted node replicates the old node before it , The old node accesses another old node according to the random pointer , The new node is also inserted after the old node accessed , Old node —— Old node and New node —— New nodes The relative distance is the same , The direction of the random pointer is determined .

The procedure is as follows ：

struct Node* copyRandomList(struct Node* head) {
    
	if(head==NULL)
    return NULL;

    // The copy node is behind the original node 
    struct Node* cur=head;
    while(cur)
    {
    
        struct Node* next=cur->next;
        struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
        copy->val=cur->val;
        cur->next=copy;
        copy->next=next;
        cur=next;
    }

    // Assign values to random nodes 
    cur=head;
    while(cur)
    {
    
        struct Node* copy=cur->next;
        if(cur->random)
        {
    
            copy->random=cur->random->next;
        }
        else
        {
    
            copy->random=NULL;
        }
        cur=copy->next;
    }

    // Link the new nodes 
    struct Node* copyhead,*copytail;
    copyhead=copytail=(struct Node*)malloc(sizeof(struct Node));
    cur=head;
    while(cur)
    {
    
        struct Node* copy=cur->next;
        struct Node* next=copy->next;

        copytail->next=copy;
        copytail=copy;

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

    struct Node* p=copyhead;
    copyhead=copyhead->next;
    free(p);
    return copyhead;
}