LeetCode707. Design linked list

LeetCode707. Design the list

1. subject

2. Ideas

There are five functions , Corresponding to the five basic operations of the linked list ： Find nodes 、 Head insertion 、 Tail insertion 、 Insert before a node 、 Delete . The following are implemented separately .

3. Code implementation

（1） Implement by function

The function interface

class MyLinkedList {
    
public:
    MyLinkedList() {
    }
    
    int get(int index) {
    }
    
    void addAtHead(int val) {
    }
    
    void addAtTail(int val) {
    }
    
    void addAtIndex(int index, int val) {
    }
    
    void deleteAtIndex(int index) {
    }
};

/** * Your MyLinkedList object will be instantiated and called as such: * MyLinkedList* obj = new MyLinkedList(); * int param_1 = obj->get(index); * obj->addAtHead(val); * obj->addAtTail(val); * obj->addAtIndex(index,val); * obj->deleteAtIndex(index); */

1. Linked list design

private:
	int size; // Chain length 
	LinkNode* dummyHead;	// Sentinel node 

2. Linked list creation and function initialization

public:
// Definition of linked list 
struct LinkNode{
    
        int val;
        LinkNode* next;
        ListNode() : val(0), next(nullptr) {
    }
     	ListNode(int x) : val(x), next(nullptr) {
    }
     	ListNode(int x, ListNode *next) : val(x), next(next) {
    }
    };
    
// Initialization of linked list 
    MyLinkedList() {
    
        dummyHead = new LinkNode(0);// Sentinel node  next The default point to NULL
		size = 0; // The length of the list is 0  Sentinel nodes are not included in the length  
    }

matters needing attention

1. Used size, Indicates the length of the list , Sentinel nodes are not included ！
2. Pay attention to the question stem ！ The subscript of the node is from 0 Start ！！！

3. Lookup function ——int get(int index) {}

// Find the first index Nodes  
 int get(int index) {
    
		if(index > (size-1) || index < 0)//index from 0 Start ！！！ therefore size Need to get 1 
	    return -1;
		LinkNode *p = dummyHead -> next;// confirm dummy There's something in the back k You can rest assured ->next
		while(index--)// First use and then subtract , Just go index Step  
			p = p->next; 
		return p->val; 
    }

matters needing attention

1. Be careful while(index–) Use , It's just right to go index Step . Can replace for.
2. another ：index Get is index-1 The value after
3. Write dummyHead->next Pay attention dummyHead Is there free in the back ！
4.index from 0 Start ！ Not from 1！

4. Head insertion node —— void addAtHead(int val) {}

void addAtHead(int val) {
    
		LinkNode* node = new LinkNode(val);
		node->next = dummyHead->next; // Insert it behind the sentinel node 
		dummyHead->next = node;
		size++;
    }

matters needing attention

Don't forget to change the length of the linked list ！

5. Tail insertion node ——void addAtTail(int val)

void addAtTail(int val) {
    
		LinkNode *p = dummyHead;// Don't point casually dummy Of next！
		while(p->next != NULL)
			p = p->next;
		LinkNode*node = new LinkNode(val);
		//node->next = p->next;// Don't write , Because in the end ！
		 p->next = node;
		 size++;
    }

matters needing attention

1. When traversing the linked list, set the pointer for traversal , Be careful if you access empty areas .

6. Insert before a specific node ——void addAtIndex(int index, int val) {}

 void addAtIndex(int index, int val) {
    
 //index < 0 The situation of 
	if(index<0){
    
		 LinkNode*node = new LinkNode(val);
		 node->next = dummyHead->next; 
		 dummyHead->next = node;
		 size++;}
		 
//index>size（ Chain length ）
	else if(index > size) return;
	
//index ==  Chain length 
	else if(index == size)
	{
    
		LinkNode *p = dummyHead;
		while(p->next != NULL)
			p = p->next;
		LinkNode*node = new LinkNode(val);
		node->next = p->next;
		 p->next = node;
		 size++;
	}
	
// Other situations 
	 else//if(index>=0 && index < size)// The conditions here are wrong , At present, I still don't know how to change ..
	{
    
		LinkNode *p = dummyHead;
		//for(int i = 0;i<index;i++)// It's the same thing as down here ！
        while(index--)	
			p = p->next;//p Point to previous node  
		LinkNode*node = new LinkNode(val);
		node->next = p->next;
		p->next = node; 
		size++;
	} 	
   }

Stick a section here Carl The big guy's question , Because many of the above situations can be combined ！

void addAtIndex(int index, int val) {
    
        if (index > _size) {
    
            return;
        }
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = _dummyHead;
        while(index--) {
    // You can use this ！
            cur = cur->next;
        }
        newNode->next = cur->next;
        cur->next = newNode;
        _size++;
    }

matters needing attention

1. In many cases, never all if, Remember to if else！！！ Otherwise, it will be troublesome if there is repetition ！
2. If the condition of one situation is troublesome , It's better to put it at the end and use it directly else
Be careful size Relationship with the following table ！ The length of the linked list is not size-1！

7. Delete —— void deleteAtIndex(int index)

    void deleteAtIndex(int index) {
    
    if(index >= size || index <0) return;// There has to be ？  No need .
	if(index <= (size-1) && index >=0)
	{
    
		LinkNode *p = dummyHead;
		//for(int i = 0;i<index;i++)
        while(index--)	// Either way 
			p = p->next;//p Point to previous node  
		LinkNode * q = p->next;
		p-> next = q->next;
		delete q;
		size--;
	}
   }

matters needing attention

1.if(index >= size || index <0) return; This sentence can be deleted .
2. The traversal pointer is still from dummyHead set out

（2） Complete code

class MyLinkedList {
    
public:
    struct LinkNode{
    
        int val;
        LinkNode* next;
        LinkNode(int x):val(x),next(nullptr){
    }
            
    };
    
    MyLinkedList() {
    
        dummyHead = new LinkNode(0);// Sentinel node 
		size = 0; // Chain length   Sentinels are not length  
    }
    
    int get(int index) {
    // Find the first index Nodes  
		if(index > (size-1) || index < 0)//index from 0 Start ！！！ therefore size Need to get 1 
	   	return -1;
		LinkNode *p = dummyHead -> next;// confirm dummy There is something in the back ->next
		while(index--)// First use and then subtract , Just go index Step  
			p = p->next; 
		return p->val; 
    }
    
    void addAtHead(int val) {
    
		LinkNode* node = new LinkNode(val);
		node->next = dummyHead->next; 
		dummyHead->next = node;
		size++;
    }
    
    void addAtTail(int val) {
    
		LinkNode *p = dummyHead;// Don't point casually dummy Of next
		while(p->next != NULL)
			p = p->next;
		LinkNode*node = new LinkNode(val);
		//node->next = p->next;
		 p->next = node;
		 size++;
    }
    
    void addAtIndex(int index, int val) {
    
	if(index<0){
    
		 LinkNode*node = new LinkNode(val);
		 node->next = dummyHead->next; 
		 dummyHead->next = node;
		 size++;
		}
	else if(index > size) return;// correct 
	else if(index == size)// It's not an empty list   By the way, it should 
	{
    
		LinkNode *p = dummyHead;
		while(p->next != NULL)
			p = p->next;
		LinkNode*node = new LinkNode(val);
		node->next = p->next;
		 p->next = node;
		 size++;
	}
	 else //if(index>=0 && index < size)// It is required to be in the index Before nodes ！
	{
    
		LinkNode *p = dummyHead;
		//for(int i = 0;i<index;i++)
        while(index--)	
			p = p->next;//p Point to previous node  
		LinkNode*node = new LinkNode(val);
		node->next = p->next;
		p->next = node; 
		size++;
	} 	
   }
    
    void deleteAtIndex(int index) {
    
    if(index >= size || index <0) return;// There has to be ？ 
	if(index <= (size-1) && index >=0)
	{
    
		LinkNode *p = dummyHead;
		//for(int i = 0;i<index;i++)
        while(index--)	// Either way 
			p = p->next;//p Point to previous node  
		LinkNode * q = p->next;
		p-> next = q->next;
		delete q;
		size--;
	}
   }
    
private:
	int size;
	LinkNode* dummyHead;
};