6. 顺序表和链表*****
目录
1. 顺序表
1.1 原理
1.2 常见的增删查改
1.3 顺序表的问题
2. 链表
2.1 原理
2.2 无头单向非循环的增删查改
2.3 链表面试题
1. 删除链表中等于给定值val的所有节点203. 移除链表元素
2. 链表逆置206. 反转链表（考的最多）
3.给你单链表的头结点 head ，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。876. 链表的中间结点
4.实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。面试题 02.02. 返回倒数第 k 个节点
5. 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 21. 合并两个有序链表
6.给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。面试题 02.04. 分割链表
7. 链表的回文结构234. 回文链表
8.给定两个单链表的头节点 headA 和 headB ，请找出并返回两个单链表相交的起始节点LCR 023. 相交链表。
9.给你一个链表的头节点 head ，判断链表中是否有环。141. 环形链表
10.给定一个链表的头节点 head ，返回链表开始入环的第一个节点。142. 环形链表 II
11. 链表深度拷贝138. 随机链表的复制
1. 顺序表
1.1 原理
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般分为：
1.静态顺序表：使用定长数组存储元素
2.动态顺序表：使用动态开辟的数组存储
1.2 常见的增删查改
typedef int SLDateType;
typedef struct SeqList
{
SLDataType* a;
size_t size;
size_t capacity;
}SeqList;
// 对数据的管理:增删查改
void SeqListDestroy(SeqList* ps)
{
free(ps->a);
ps->a = NULL;
ps->capacity = ps->size = 0;
}
void SeqListCheck(SeqList *ps)
{
if(ps->size == ps->capacity)
{
SLDateType *tmp = (SLDateType*)realloc(ps->a,sizeof(SLDateType)*ps->capacity*2);
if(tmp == NULL)
{
perror("realloc fail");
return;
}
ps->a = tmp;
ps->capacity *= 2;
}
}
void SeqListPushBack(SeqList* ps, SLDateType x)
{
SeqListCheck(ps);
ps->a[ps->size++] = x;
}
void SeqListPushFront(SeqList* ps, SLDateType x)
{
assert(ps);
SeqListCheck(ps);
int end = ps->size-1;
while(end >= 0)
{
ps->a[end+1] = ps->a[end];
end--;
}
ps->a[0] = x;
ps->size++;
}
void SeqListPopFront(SeqList* ps)
{
assert(ps);
assert(ps->size>0);
int begin = 0;
while(begin<ps->size)
{
ps->a[begin] = ps->a[begin+1];
begin++;
}
ps->size--;
}
void SeqListPopBack(SeqList* ps)
{
assert(ps->size>0);
ps->size--;
}
// 顺序表查找
int SeqListFind(SeqList* ps, SLDateType x)
{
assert(ps);
int i = 0;
for(i=0; i<ps->size; i++)
{
if(ps->a[i]==x)
{
return i;
}
}
return -1;
}
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDateType x)
{
assert(ps);
assert(pos >= 0 && pos <=ps->size);
SeqListCheck(ps);
int end = ps->size-1;
while(end >=pos)
{
ps->a[end+1] = ps->a[end];
end--;
}
ps->a[pos] = x;
ps->size++;
}
// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos)
{
assert(ps);
assert(pos >=0 && pos <= ps->size);
int begin = pos+1;
while(begin<ps->size)
{
ps->a[begin-1] = ps->a[begin];
begin++;
}
ps->size--;
}
顺序表的所有操作都是基于数组下标完成的，不需要修改数组的起始地址，因此不需要使用二级指针。
1.3 顺序表的问题
1. 中间、头部的插入删除，时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间，会有不小的消耗
3.增容一般呈2倍的增长，肯定会有空间的浪费，比如当前容量是100， 满了以后增容到200，我们再插入2个数据，那么就浪费了98个数据空间。
链表解决了以上问题。
2. 链表
2.1 原理
链表是一种物理存储上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表与顺序表相辅相成。
链表的种类有很多种：
带头/不带头，单向/双向，循环/非循环，互相组合共有8种。我们常用就两种：无头单向非循环、带头双向循环链表（尾→next指向哨兵位的头，哨兵位的prev指向尾）。
1.无头单向非循环：结构简单，一般不会用来单独存数据，实际更多是作为其他数据结构的子结构，如哈希桶等。另外这种结构在笔试面试中出现很多。
2.带头双向循环链表：结构最复杂，一般用于单独存储数据，实际中使用的链表都是带头双向循环链表。
2.2 无头单向非循环的增删查改
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType data;
struct SListNode* next;
}SListNode;
// 动态申请一个节点
SListNode *BuySListNode(SLTDateType x)
{
SListNode *newnode = (SListNode*)malloc(sizeof(SListNode));
if(newnode == NULL)
{
perror("malloc fail:");
return NULL;
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
// 单链表打印
void SListPrint(SListNode* plist)
{
SListNode *cur = plist;
while(cur!=NULL)
{
printf("%d->",cur->data);
cur = cur->next;
}
printf("NULL");
}
// 单链表尾插
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 SListPushFront(SListNode** pplist, SLTDateType x)
{
SListNode *newnode = BuySListNode(x);
newnode->next = *pplist;
*pplist = newnode;
}
// 单链表的尾删
void SListPopBack(SListNode** pplist)
{
assert(pplist);//如果 pplist 为 NULL，说明调用者传入了一个无效的指针，后续对 *pplist 的解引用会导致程序崩溃（解引用空指针是未定义行为）。
assert(*pplist);//检查链表是否为空
if((*pplist)->next == NULL)
{
free(*pplist);
*pplist = NULL;
}
else
{
SListNode *prev = NULL;
SListNode *tail = *pplist;
while(tail->next !=NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
tail = NULL;
prev->next = NULL;
}
}
// 单链表头删
void SListPopFront(SListNode** pplist)
{
assert(pplist);
SListNode *first = *pplist;
*pplist = first->next;
free(first);
first = NULL;
}
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
SListNode *cur = plist;
while(cur != NULL)
{
if(cur->data == x)
{
return cur;
}
else
{
cur = cur->next;
}
}
return NULL;
}
// 分析思考为什么不在pos位置之前插入？
// 答：需要pos前的next指向插入的newnode，但pos前一个位置只能从头才能找到。
// 单链表在pos位置之后插入x。
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
assert(pos);
SListNode *newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
// 分析思考为什么不删除pos位置？答：同理需要找到pos前一个位置
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
assert(pos);
assert(pos->next);
SListNode *del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}
// 在pos的前面插入
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x)
{
assert(pos);
assert(*pphead);
if(pos == *pphead)
{
SListPushFront(pphead, x);
}
else
{
SListNode *prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
SListNode *newnode = BuySListNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
// 删除pos位置
void SLTErase(SListNode** pphead, SListNode* pos)
{
assert(pphead);
assert(pos);
if(*pphead == NULL)
{
SListPopFront(pphead);
}
else
{
SListNode *prev = *pphead;
while(prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
}
}
void SLTDestroy(SListNode *phead)
{
SListNode *cur = phead;
while(cur != NULL)
{
SListNode *tmp = cur->next;
free(cur);
cur = tmp;
}
}
单链表：在增删节点时，可能需要修改头指针本身（例如删除头节点或插入新头节点），因此需要使用二级指针来修改头指针的地址。
双向带头循环链表：由于头节点固定且循环，增删操作通常只需要修改节点的前驱和后继指针，不需要修改头节点本身，因此不需要二级指针。
2.3 链表面试题
1. 删除链表中等于给定值val的所有节点203. 移除链表元素
class Solution
{
public:
ListNode* removeElements(ListNode* head, int val)
{
ListNode* cur = head;//保存头节点
ListNode* prev = nullptr;
while(cur != nullptr)//遍历链表
{
if(cur->val == val)
{
if(prev == nullptr)//头删情况-第一个就是val-直接删，head指向下一个位置
{
head = cur->next;
delete cur;
cur = head;
}
else
{
prev->next = cur->next;
delete cur;
cur = prev->next;
}
}
else
{
prev = cur;
cur = cur->next;
}
}
return head;
}
};2. 链表逆置206. 反转链表（考的最多）
方法一：遍历
class Solution
{
public:
ListNode* reverseList(ListNode* head)
{
ListNode* newhead = new ListNode(0);
ListNode* cur = head;
while(cur)
{
ListNode* next = cur->next;
cur->next = newhead->next;
newhead->next = cur;
cur = next;
}
cur = newhead->next;
delete newhead;
return cur;
}
};方法二：递归
class Solution
{
public:
ListNode* reverseList(ListNode* head)
{
if(head == nullptr || head->next == nullptr)//如果是一个节点，直接返回
return head;
ListNode* newnode = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return newnode;
}
};3.给你单链表的头结点 head ，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。876. 链表的中间结点
快慢指针：
class Solution
{
public:
ListNode* middleNode(ListNode* head)
{
ListNode* slow = head;
ListNode* fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
};4.实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。面试题 02.02. 返回倒数第 k 个节点
//倒数第k个到最后一个的距离是k-1，让slow和fast的距离也是k-1，fast走到最后时slow就是倒数第k个
class Solution
{
public:
int kthToLast(ListNode* head, int k)
{
ListNode* slow = head;
ListNode* fast = head;
while(--k)//--k走k-1步，k--是走k步
{
fast = fast->next;
}
while(fast->next != nullptr)
{
slow = slow->next;
fast = fast->next;
}
return slow->val;
}
};5. 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 21. 合并两个有序链表
方法一：迭代
class Solution
{
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)
{
ListNode* newhead = new ListNode(0);
ListNode* prev = newhead;
ListNode* cur1 = list1;
ListNode* cur2 = list2;
while(cur1 && cur2)
{
if(cur1->val <= cur2->val)
{
prev->next = cur1;
cur1 = cur1->next;
}
else
{
prev->next = cur2;
cur2 = cur2->next;
}
prev = prev->next;
}
while(cur1)
{
prev->next = cur1;
cur1 = cur1->next;
prev = prev->next;
}
while(cur2)
{
prev->next = cur2;
cur2 = cur2->next;
prev = prev->next;
}
prev = newhead->next;
delete newhead;
return prev;
}
};方法二：递归
class Solution
{
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)
{
if(list1 == nullptr || list2 == nullptr)
{
return list1 == nullptr ? list2 : list1;
}
ListNode* newnode = list1->val > list2->val ? list2 : list1;
if(newnode == list1)
{
newnode->next = mergeTwoLists(list1->next, list2);
}
else
{
newnode->next = mergeTwoLists(list1, list2->next);
}
return newnode;
}
};6.给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。面试题 02.04. 分割链表
class Solution
{
public:
ListNode* partition(ListNode* head, int x)
{
if(head==nullptr || head->next==nullptr)
return head;
ListNode* lessnode = new ListNode(0);
ListNode* bignode = new ListNode(0);
ListNode* lesshead = lessnode;
ListNode* bighead = bignode;
ListNode* cur = head;
while(cur)
{
if(cur->val < x)
{
lesshead->next = cur;
cur = cur->next;
lesshead = lesshead->next;
lesshead->next = nullptr;
}
else
{
bighead->next = cur;
cur = cur->next;
bighead = bighead->next;
bighead->next = nullptr;
}
}
lesshead->next = bignode->next;
cur = lessnode->next;
delete lessnode;
delete bignode;
return cur;
}
};7. 链表的回文结构234. 回文链表
为什么不整体翻转然后比较两个头节点：
reverseList 函数会修改原始的链表结构，导致在 isPalindrome 函数中比较时出现问题。具体来说，reverseList 函数会将链表反转，并且将原始链表的 head 节点的 next 指针设置为 nullptr，这会导致原始链表被破坏。
所以只反转一半：
class Solution
{
ListNode* reverseList(ListNode* head)
{
if(head==nullptr || head->next==nullptr)
return head;
ListNode* newhead = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return newhead;
}
public:
bool isPalindrome(ListNode* head)
{
ListNode* slow = head;
ListNode* fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
ListNode* mid = slow;//两个中间则是后面那个
ListNode* newhead = reverseList(mid);
while(head && newhead)
{
if(head->val != newhead->val)
return false;
head = head->next;
newhead = newhead->next;
}
return true;
}
};原来 1->2->3->2->1
null
↑
逆置一半：1->2->3<-2<-18.给定两个单链表的头节点 headA 和 headB ，请找出并返回两个单链表相交的起始节点LCR 023. 相交链表。
class Solution
{
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
{
int n1 = 0, n2 = 0;
ListNode* cur = headA;
while(cur)
{
n1++;
cur = cur->next;
}
cur = headB;
while(cur)
{
n2++;
cur = cur->next;
}
ListNode* fast = headB;
ListNode* slow = headA;
if(n1 > n2)
{
fast = headA;
slow = headB;
}
int gap = abs(n1-n2);
while(gap--)
{
fast = fast->next;
}
while(slow && fast)
{
if(slow == fast)
return slow;
slow = slow->next;
fast = fast->next;
}
return nullptr;
}
};9.给你一个链表的头节点 head ，判断链表中是否有环。141. 环形链表
class Solution
{
public:
bool hasCycle(ListNode *head)
{
ListNode* slow = head;
ListNode* fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
return true;
}
return false;
}
};证明：
fast一定先进环，当slow进环时，假设fast距离slow有N步，此时slow走N步，fast走2N步，正好能追得上。但是fast一次走3步，4步...是不行的。假设两个元素构成一个环，每次追两步是永远不会相遇的。
10.给定一个链表的头节点 head ，返回链表开始入环的第一个节点。142. 环形链表 II
class Solution
{
public:
ListNode *detectCycle(ListNode *head)
{
ListNode* slow = head;
ListNode* fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
{
ListNode* meet = slow;
ListNode* sta = head;
while(sta != meet)
{
sta = sta->next;
meet = meet->next;
}
return meet;
}
}
return nullptr;
}
};证明：
11. 链表深度拷贝138. 随机链表的复制
class Solution
{
public:
Node* copyRandomList(Node* head)
{
Node* cur = head;
while(cur)//每个结点后链接拷贝结点
{
Node* copy = new Node(cur->val);
Node* next = cur->next;
cur->next = copy;
copy->next = next;
cur = next;
}
cur = head;
while(cur)//拷贝random关系
{
Node* copy = cur->next;
if(cur->random == nullptr)
copy->random = nullptr;
else
copy->random = cur->random->next;
cur = copy->next;
}
Node* copynode = new Node(0);
Node* copyhead = copynode;
cur = head;
while(cur)//恢复head和解下copy结点
{
Node* copy = cur->next;
Node* next = copy->next;
copyhead->next = copy;
copyhead = copy;
cur->next = next;
cur = next;
}
cur = copynode->next;
delete copynode;
return cur;
}
};