1、单链表的增删查改
#include "slist.h"
SListNode*BuySListNode(SLTDateType x)
{
SListNode*node = (SListNode*)malloc(sizeof(SListNode));
node->data = x;
node->next = NULL;
return node;
}
void SListPrint(SListNode*plist)
{
SListNode*cur = plist;
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
void SListPushBack(SListNode**pplist, SLTDateType x)
{
SListNode*newnode = BuySlistNode(x);
if (*pplist == NULL)
{
*pplist == newnode;
}
else
{
SListNode*tail = *pplist;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
void SListBack(SListNode**pplist)
{
SListNode*prev = NULL;
SListNode*tail = *pplist;
if (tail == NULL || tail->next == NULL)
{
free(tail);
*pplist = NULL;
}
else
{
while (tail->next)
{
prev = tail;
tail = tail -> next;
}
free(tail);
tail = NULL;
prev->next = NULL;
}
}
void SListPushFront(SListNode**pplist, SLTDateType x)
{
assert(pplist);
SListNode*newode = BuySListNode(x);
if (*pplist == NULL)
{
*pplist = newnode;
}
else
{
newnode->next = *pplist;
*pplist = newnode;
}
}
void SListPopFront(SListNode**pplist)
{
SListNode*first = *pplist;
if (first == NULL)
{
return;
}
else if (first->next == NULL)
{
free(first);
*pplist = NULL;
}
else
{
SListNode*next = first->next;
free(first);
*pplist = next;
}
}
SListNode*SListFind(SListNode*pplist, SLTDateType x)
{
SListNode*cur = plist;
while (cur)
{
if (cur->data == x)
return cur;
cur = cur->next;
}
return NULL;
}
void SListInsertAfter(SListNode*pos, SLTDateType x)
{
assert(pos);
SListNode*next = pos->next;
SListNode*newnode = BuySListNode(x);
pos->next = newnode;
newnode->next = next;
}
void SListEraseAfter(SListNode*pos)
{
assert(pos);
SListNode*next = pos->next;
if (next != NULL)
{
SListNode*nextnext = next->next;
free(next);
pos->next = nextnext;
}
}
2、给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
C语言：
struct ListNode*removeElements(struct ListNode*head, int val)
{
if (head == NULL)
{
return head;
}
head->next = removeElements(head->next, val);
{
return head->val == val ? head->next : head;
}
}
c++：
class Solution
{
public:
ListNode*removeElements(ListNode*head, int val)
{
if (head == nullptr)
{
return head;
}
head->next = removeElements(head->next, val);
return head->val == val ? head->next : head;
}
};
首先对单链表是否是空的进行判断，此后将数值进行一个判断即刻。
3、反转一个单链表
C语言
struct ListNode*reverseList(struct ListNode*head)
{
struct ListNode*prev = NULL;
struct ListNode*curr = head;
while (curr)
{
struct ListNode*next = curr->next;
curr->next = prev;
pre = curr;
curr = next;
}
return prev;
}
c++
class Solution
{
public:
ListNode* reverseList(ListNode*head)
{
ListNode*next = nullptr;
ListNode*curr = head;
while (curr)
{
ListNode*next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
rerurn prev;
}
};
对单链表进行遍历，定义pre和curr两个指针实现链表反转。
4、给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点
c++
class Solution
{
public:
ListNode*middleNode(ListNode*head)
{
vector<ListNode*>A = { head };
while (A.back()->next != NULL)
A.push_back(A.back()->next);
return A[A.size() / 2];
}
};
链表具有缺点不能通过下标访问对应的元素，因此我们直接对链表进行一个遍历，将元素放到数组中，对应求出元素的个数，[A.size()/2]就能将中间元素求出。