catalogue

1, Key points of this chapter

3.1 dynamically apply for a node

3.3 single chain table tail insertion

3.4 head insertion of single chain table

3.5 tail deletion of single linked list

3.6 deletion of single chain header

3.8 single linked list insert x before pos position

3.9 deleting nodes at pos position in single linked list

4, Online oj training

4.1 remove linked list elements (force buckle)

# 1, Key points of this chapter

3. Online oj training

# 2, Introduction to linked list

Concept: linked list is a non continuous and non sequential storage structure in physical storage structure. The logical order of data elements is through linked list

Simply put: a linked list is a list of structures associated with each other, and the means of association is a pointer. By storing the address of the next structure, you can access the data in the structure one by one.

Compared to the sequence table. Linked list can solve some shortcomings of sequential list.

1. From the perspective of memory: both static sequential table and dynamic sequential table will have a certain memory waste. The linked list uses one node to apply for one node without memory waste.
2. From the perspective of efficiency: the sequence table moves data whether it is header insertion or intermediate insertion and deletion, and the time complexity is O (N). The linked list can be inserted and deleted as long as the pointer is changed.

There are 8 kinds of actual linked list structures to be combined:

1. Unidirectional and bidirectional
2. Take the lead or not
3. Circulation and non circulation

There is a sentinel node, which does not store any valid data and belongs to an invalid node. However, using this invalid node as the head node will have some advantages in some aspects.

For example, when you insert a new node, you don't need to pass the secondary pointer, because our head node always points to this invalid node.

Two way:

It means that there is no longer only one pointer in the node, but two pointers, one pointing to the previous node and the other pointing to the next node.

Cycle:

The tail pointer no longer points to NULL, but to the head node.

# 3, Implementation of common interfaces for headless one-way acyclic linked list

## 3.1 dynamically apply for a node

```SLTNode* BuySListNode(SLDataType x)
{
SLTNode* newnode = malloc(sizeof(SLTNode));
if (newnode == NULL)
{
printf("malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}```

## 3.2 single linked list printing

```void SListPrint(SLTNode* phead)
{
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}```

## 3.3 single chain table tail insertion

```void SListPushBack(SLTNode** pphead, SLDataType x)
{
{
return;
}
else
{
SLTNode* tail;
while (tail->next)
{
tail = tail->next;
}
return;
}
}```

## 3.4 head insertion of single chain table

```void SListPushFront(SLTNode** pphead, SLDataType x)
{
}```

## 3.5 tail deletion of single linked list

```void SListPopBack(SLTNode** pphead)
{
{
return;
}
{
}
else
{
SLTNode* prev = NULL;
while (tail->next)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
}```

## 3.6 deletion of single chain header

```void SListPopFront(SLTNode** pphead)
{
{
return;
}
else
{
free(temp);
}
}```

## 3.7 single linked list lookup

```SLTNode* SListSearch(SLTNode* phead, SLDataType x)
{
{
{
}
}
return NULL;
}```

## 3.8 single linked list insert x before pos position

```void SListInsert(SLTNode** pphead, SLTNode* pos, SLDataType x)
{
{
return;
}
{
newnode->next = pos;
}
else
{
while (cur->next != pos)
{
cur = cur->next;
}
newnode->next = pos;
cur->next = newnode;
}
}```

## 3.9 deleting nodes at pos position in single linked list

```void SListErase(SLTNode** phead, SLTNode* pos)
{
{
return;
}
{
}
else
{
while (cur->next != pos)
{
cur = cur->next;
}
cur->next = pos->next;
free(pos);
}
}```

# 4, Online oj training

### 4.1 remove linked list elements (force buckle)

Give you a head node ， head ， and an integer ， val of the linked list. Please delete all ， nodes in the linked list val = = val's node and returns a new header node.

```Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]

Input: head = [7,7,7,7], val = 7
Output: []```

Idea:

Before and after pointers (attendant pointers), the initial state transition prev points to NULL and cur points to head. If cur - > Val = = val

Delete. The deletion steps are prev - > next = = cur - > next; cur=cur->next. The iterative process is: prev = cur, cur = = cur - > next.

In special cases, if the val to be deleted is the head node, the deletion steps are head = cur - > next; free(cur); cur=head.

Code reference:

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

```Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]```
```Input: head = []
Output: []```

```typedef struct ListNode ListNode;
{
if(cur==NULL)
{
return cur;
}
ListNode* next=cur->next;
while(cur)
{
cur=next;
if(next)
next=next->next;
}
}```

Note: the end condition is cur==NULL; At this time, if next moves backward, next = next - > next; NULL dereference will occur.

Secondly, consider the problem of cur==NULL. Otherwise, listnode * next = cur - > next is also a dereference to null pointers.

In fact, it can be reduced to:

```struct ListNode* reverseList(struct ListNode* head)
{