Basic operation and question type summary of linked list

1. Basic operations of linked lists

1.1 Create a linked list

#include<stdio.h>
#include<malloc.h>
typedef struct node
{
    
	int data;
	struct node *link;
}LNode,*LinkList;

LinkList create(int n) // Create a linked list 
{
    
	LinkList p,r,list=NULL; //r Is the first element node 
	for(int i=0;i<n;i++)//n It's the number of elements 
	{
    
		p=(LinkList)malloc(sizeof(LNode));// Allocate space to the linked list 
		p->data=i;// Assignment element 
		p->link=NULL;
		if(list==NULL)
		{
    
			list=p;
		}
		else
		{
    
			r->link=p; // Connect the new node to the end of the linked list 
		}
		r=p; //r Always point to the end 
	}
	return list;
}

1.2 Find the length of the linked list

 General algorithm 
int Length(LinkList list)
{
    
	LinkList p=list;
	int sum=0;
	while(p!=NULL)
	{
    
		sum++;
		p=p->link;
	}
	return sum;
}

 A recursive algorithm 
int Length(LinkList list)
{
    
	if(list!=NULL)
	{
    
		return 1+Length(list->link);// To add the root node 
	}
	else
	{
    
		return 0;
	}
}

1.3 Determine the elements item Position in the linked list

LinkList Find(LinkList list,int item)
{
    
	LinkList p=list;
	while(p!=NULL && p->data!=item)
	{
    
		p=p->link;
	}
	return p;
}

1.4 The information inserted at the first link point of the non empty linked list is item The node of

// Ideas ： Create a new link point and insert it into the linked list 
void InsertLink1(LinkList &list,int item)// Be careful to quote , Because you want to change the elements of the linked list 
{
    
	LinkList p;
	p=(LinkList)malloc(sizeof(LNode));
	p->data=item;
	p->link=list;
	list=p;//list Point to new node 
}

1.5 Insert the information at the end of the non empty column as item Link point for

void InsertLink2(LinkList list,int item)
{
    
	LinkList p,r;
	r=list;
	while(r->link!=NULL)
	{
    
		r=r->link;
	}// Find the address of the node at the end of the linked list 
	p=(LinkList)malloc(sizeof(LNode));
	p->data=item;
	p->link=NULL;
	r->link=p;
}

1.6 Reverse a linear linked list

// Iterative method 
LinkList reverse(LinkList list)
{
    
	if(list==NULL)
	{
    
		return NULL;
	}
	LinkList pre=NULL,cur=list,next;
	// The three pointers represent the previous node , Current node and next node 
	while(cur)
	{
    
		next=cur->link;// Save the next node of this node in the linked list 
		cur->link=pre;// Change the direction 
		pre=cur;
		cur=next;
	}
	return pre;// here pre Point to the last node 
}

// Recursive method 
   LinkList reverseList ( LinkList list )
    {
    
        if (list == NULL ||list -> link ==NULL ) 
			returnlist ;
       
        LinkList p = reverseList (list -> link ); 
		// Recursion is followed by a shift from back to front 
       list -> link -> link =list ;
       list -> link = NULL ;
        return p ;
    }

1.7 Destroy the list

void Delete(LinkList &list)
{
    
	LinkList p=list;
	while(p!=NULL)
	{
    
		list=p->link;
		free(p);
		p=list;
	}
}

1.8 Connect the two linked lists

{
    
	ListLink p;
	p=list1;
	while(p!=NULL)
	{
    
		p=p->link;
	}
	p->link=list2;
}

1.9 Copy a linked list

LinkList Copy(LinkList list)
{
    
	LinkList lista;
	if(list==NULL)
	{
    
		return NULL;
	}
	else
	{
    
		lista=(LinkList）malloc(sizeof(TNode));
		lista->data=list->data;
		lista->link=Copy(list->link);
	}
	return lista;
}
	 

1.91 Move the link point with the largest data field in the linked list to the end of the linked list

// Using a double pointer p,q
void Remove(LinkList &list)  
{
    
	LinkList p=list,q=list->link;//q Is the node of the maximum value of the data field 
	LinkList r=list,s;//s Is the precursor node of the maximum value 
	while(p!=NULL)
	{
    
		if(p->data>q->data)
		{
    
			s=r;//s The precursor node that points to the maximum node 
			q=p;//q Point to the maximum node 
		}
		r=p;
		p=p->link;//p Move to the next node 
	}
	if(q!=r)// If the largest node of the data field is not the end 
	{
    
		if(q==list)// If it is a header node 
			list=list->link;
		else
			s->link=q->link;
		    r->link=q;//r It's the tail node , Point the next node of the tail node to q, here q It's the tail node 
			q->link=NULL;// Null the pointer field of the new end node 
	}
}

2. The question type summary of the linked list

2.1 Circular linked list

Definition ： From any chain node in the table, you can access other nodes of the table .
Be careful ： It is convenient to solve the problem , You can judge to look for the last element , Set a special node in front of the first chain node in the linked list , Head node , The data field of the header node can be left blank , You can also store information such as the length of the linked list .

// To establish a single chain table by tail insertion , And let the pointer field of the last node point to the header node 
void CreateFromTail(LinkList list)// To establish a single chain table by tail insertion 
{
    
 TNode *s, *rear;
 int i;
 rear = (TNode *)list;
 int flag = 1;
 while (flag)
 {
    
  scanf("%d", &i);
  if (i != -1)
  {
    
   s = (TNode *)malloc(sizeof(TNode));
   s->data = i;
   rear->link = s;
   rear = s;
  }
  else
  {
    
   flag = 0;
   
  }
 }
 rear->link = list;
}

2.2 Add and subtract univariate polynomials

#include<iostream>
using namespace std;
typedef struct Node
{
    
	int coef;// coefficient 
	int exp;// Number of items 
	struct Node *link;
}TNode,* LinkList;

LinkList create(int coef,int exp)// Create a linked list 
{
    
	 LinkList p,r,list=NULL;
	 p=(LinkList)malloc(sizeof(TNode));
	 p->coef=coef;
	 p->exp=exp;
	 p->link=NULL;
	 if(list==NULL)
		 list=p;//list Is the head node 
	 else
	 {
     
		 r->link=p;//r Always point to the end of the linked list 
	 }
	 r=p;
	 return (list);
}

// Add a node 
LinkList Add(LinkList list,int ep,int cof)
{
    
	LinkList w;
	w=(LinkList)malloc(sizeof(TNode));
	w->coef=cof;
	w->exp=ep;
	list->link=w;
	return w;// Returns the last position of the current linked list node 
}

// Polynomial addition 
LinkList Padd(LinkList list1,LinkList list2)
{
    
	LinkList c;// Store the added elements 
	LinkList r,p=list1,q=list2;
	int x;
	c=(LinkList)malloc(sizeof(TNode));
	r=c;//r Always point to the linked list c End node of 
	while(p!=NULL && q!=NULL)
	{
    
		if(p->exp==q->exp)// The same number of items is added 
		{
    
			x=p->coef+q->coef;// Add the corresponding coefficients 
			if(x!=0)// If the result of adding is not zero 
			{
    
				r=Add(r,p->exp,x);// Add a new term to the polynomial 
				q=q->link;
				p=p->link;
			}
		}
		if(p->exp<q->exp)
		{
    
			r=Add(r,q->exp,q->coef);
			q=q->link;
		}
		else
		{
    
			r=Add(r,p->exp,p->coef);
			p=p->link;
		}
	}
	while(p!=NULL)// take p Add the remaining items 
	{
    
		r=Add(r,p->exp,p->coef);
		p=p->link;
	}
	while(q!=NULL)// take q Add the remaining items 
	{
    
		r=Add(r,q->exp,q->coef);
		q=q->link;
	}
	r->link=NULL;// here r Points to the last element, so the pointer after it is the element 
	c=c->link;// here c Point to the first item of the linked list 
	free(p);
	return c;
}


// Polynomial subtraction 
LinkList Psub(LinkList list1,LinkList list2)
{
    
	LinkList c;// Store subtracted elements 
	LinkList r,p=list1,q=list2;
	int x;
	c=(LinkList)malloc(sizeof(TNode));
	r=c;//r Always point to the linked list c End node of 
	while(p!=NULL && q!=NULL)
	{
    
		if(p->exp==q->exp)
		{
    
			x=p->coef-q->coef;
			if(x!=0)
			{
    
				r=Add(r,p->exp,x);// Add a new term to the polynomial 
				q=q->link;
				p=p->link;
			}
		}
		if(p->exp<q->exp)
		{
    
			r=Add(r,q->exp,q->coef);
			q=q->link;
		}
		else
		{
    
			r=Add(r,p->exp,p->coef);
			p=p->link;
		}
	}
	while(p!=NULL)
	{
    
		r=Add(r,p->exp,p->coef);
		p=p->link;
	}
	while(q!=NULL)
	{
    
		r=Add(r,q->exp,q->coef);
		q=q->link;
	}
	r->link=NULL;// here r Points to the last element, so the pointer after it is the element 
	c=c->link;// here c Point to the first item of the linked list 
	free(p);
	return c;
}


void Print(LinkList list)
{
    
	LinkList p=list;
	while(p!=NULL)
	{
    
		cout<<p->coef<<"x^"<<p->exp<<"+";
		p=p->link;
	}
}

2.3 Print linked list from end to end

// Law 1 ： Make use of the first in the first out of the stack 

struct Node 
{
    
    int data;
    struct ListNode *next;
    ListNode(int x) :
      data(x), next(NULL) {
    
        }
  }ListNode,*ListLink;
vector<int> Print_List(ListLink list)
{
    
	stack<ListLink> node;
	ListLink p=list;
	while(p!=NULL)
	{
    
		node.push(p);// Stack the linked list nodes 
		p=p->next;
	}
	vector<int> result;// Store results 
	while(!node.empty())
	{
    
		p=node.top();
		result.push_back(p->data);
		node.pop();
	}
	return result;
}

// Law two ： Reverse the list 
 LinkList reverse(LinkList list)
{
    
	if(list==NULL)
	{
    
		return NULL;
	}
	LinkList pre=NULL,cur=list,next;
	// The three pointers represent the previous node , Current node and next node 
	while(cur)
	{
    
		next=cur->link;// Save the next node of this node in the linked list 
		cur->link=pre;// Change the direction 
		pre=cur;
		cur=next;
	}
	return pre;// here pre Point to the last node 
}
 void Print_List(LinkList list)
 {
    
	 LinkList p=list;
	 while(p!=NULL)
	 {
    
		 cout<<p->data<<" ";
		 p=p->link;
	 }
 }

2.4 Merge two ordered lists

Example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

LinkList Merge_Two_Lists ( LinkList list1 , LinkList list2 )
    {
    
        if ( list1 == NULL ) 
           return list2 ;
        if ( list2 == NULL ) 
           return list1 ;
       
        ListNode prehead ( 0 ); // Add a node before the head node （  When the original chain header node may change, you can consider using prehead ）
        LinkList p = & prehead ; // New linked list node pointer 
        for (; list1 != nullptr && list2 != nullptr ; p = p->next ) // Compare list1 and list2 Size of each node , Merger 
        {
    
            if ( list1 -> data < list2 -> data )
            {
    
                p ->next = list1 ; // The next node points to list1 node 
                list1 = list1->next;
            }
            else
            {
    
                p -> next = list2 ;
                list2 = list2 -> next ;
            }
        }
       
        if ( list1 != nullptr ) 
			p->next = list1 ; // Process the remaining nodes 
        if ( list2 != nullptr ) 
			p -> next = list2 ;
        return prehead.next; // Returns the head node pointer 
    }
    // expand ： Merging two ordered arrays is a similar idea 

2.5Add Two Numbers

Title Description ：
Example
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807

Ideas ： First of all, think of using a flag bit to save carry , Add the elements of the corresponding positions of the two linked lists in turn , In addition, pay attention to judge whether the two linked lists have reached the end .

LinkList AddTwoNumbers(LinkList a1,LinkList a2)
{
    
	ListNode preHead(0);
	LinkList p=&preHead;// Head node , Used to save the first node pointer , And initialization p,p It's a new linked list , Store the added data 
    int flag = 0 ; // carry 
	while(a1 || a2 || flag)
	{
    
		int sum=(a1?a1->data :0)+(a2?a2->data :0)+flag;
		// Corresponding bit addition , Determine whether it is null , Add if empty 0
		flag=sum/10;// Save carry 
		p->next=(LinkList)malloc(sizeof(ListNode));
		p->data=sum%10;
		// Create a new node , And the assignment 
		p=p->next;
		a1 = a1 ? a1 -> next : a1 ; // If it is empty , Is still empty , If not be empty , Point to the next node 
        a2 = a2 ? a2 -> next : a2 ; 
     }
        return preHead.next ; // Returns the first node pointer 
       
}

2.6Odd Even Linked List

Title Description ： Put all odd number nodes in the linked list to the front , Even nodes are put behind
Example 1:
Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL
Example 2:
Input: 2 ->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL
Ideas ： This question is related to the array, put the odd number in front , Even numbers come back like , But the array puts values , The linked list contains nodes . This problem sets up two linked lists , One stores odd numbers and one stores even numbers , Then connect the two linked lists .

LinkList Odd_NumberEven_Number ( LinkList list )
{
    
        if (! list ) 
			return list ;
        LinkList Odd_Number = list ; 
		//  Odd sequence node pointer and header pointer 
        LinkList Even_Number = list -> next ,even = Even_Number ;
		//  Even sequence node pointer and header pointer 
        while ( even && even->next ) 
		//  Even sequence pointer judgment  (  The following pointer is usually used to judge whether to end the loop )  For a two-step pointer p Need to judge p And p->next Is it empty 
        {
    
            Odd_Number -> next = Odd_Number -> next -> next ; 
			//  Connect odd sequence nodes  ,  Take two steps at a time  , Connect the previous pointer first 
            even -> next = even -> next -> next ; 
			//  Connect even sequence nodes 
           
            Odd_Number = Odd_Number -> next ; 
			//  Point to the next odd node 
            even = even -> next ;
        }
        Odd_Number -> next = Even_Number ; 
		//  Connect odd sequence linked list and even sequence linked list 
        return list ;
       
    }

2.7 The penultimate in a linked list k Nodes

Title Description ： Enter a linked list , Output the penultimate of the list K Nodes ,
Adding a linked list has 6 Nodes , Namely 1,2,3,4,5,6. The last of the list 3 The number is a value of 4 The node of .

General ideas ： Suppose the linked list has n Nodes , So the last one k The first node is from the beginning to the end n-k+1 Step by step , So how to get n Well , Just traverse the linked list from the beginning , After each passing node counter +1 That's all right. , That is to say, it needs to traverse twice , The complexity is O(n^2).

Optimization idea ： Double finger needling , The first pointer starts from the beginning k-1 Step , The second pointer stays still , From k Step on , The second pointer also starts traversing from the beginning , When the first pointer reaches the end , The second pointer happens to be the k Nodes .

ListLink FindkthtoTail(ListLink head,int k)
{
    
	if(head==NULL || k==0)
		return NULL;
	ListLink phead=head;
	ListLink pbehind=NULL;
	for(int i=0;i<k-1;i++)// The first pointer goes first k-1 Step 
	{
    
		phead=phead->next;
	}
	pbehind=head;
	while(phead->next!=NULL)
	{
    
		phead=phead->next;
		pbehind=pbehind->next;
	}
	return pbehind;
}

The lines ： When we can't solve the problem by traversing with one pointer, we can try to traverse the linked list with two pointers , You can make one of the pointers faster , For example, take two steps in the linked list at a time or take several steps in the linked list first .