1. Введение
Алгоритм работы односвязного списка — относительно частый вопрос на письменном тестовом собеседовании. В этой статье основное внимание будет уделено вопросам применения связанных списков, которые обычно используются на собеседованиях. Надеюсь, это поможет вам ^_^
2 Вывести K-й узел снизу односвязного списка
2.1 Описание проблемы
Вопрос: Введите односвязный список и выведите K-й узел из нижней части связанного списка. (Удалите головной узел, количество узлов начинается с 1)
2.2 Метод двух обходов
2.2.1 Идеи решения проблем
(1) Пройдите по односвязному списку и одновременно получите длину N связанного списка. (2) Перейдите снова с самого начала и посетите N-K-й узел в качестве желаемого узла.
2.2.2 Графический процесс
2.2.3 Реализация кода
/*计算链表长度*/
int listLength(ListNode* pHead){
int count = 0;
ListNode* pCur = pHead->next;
if(pCur == NULL){
printf("error");
}
while(pCur){
count++;
pCur = pCur->pNext;
}
return count;
}
/*查找第k个节点的值*/
ListNode* searchNodeK(ListNode* pHead, int k){
int i = 0;
ListNode* pCur = pHead;
//计算链表长度
int len = listLength(pHead);
if(k > len){
printf("error");
}
//循环len-k+1次
for(i=0; i < len-k+1; i++){
pCur = pCur->next;
}
return pCur;//返回倒数第K个节点
}
Использование этого метода обхода требует двух обходов связанного списка, а временная сложность составляет O (n * 2). Видно, что этот способ самый простой и понятный, но малоэффективный.
2.3 Рекурсивный метод
2.3.1 Идеи решения проблем
(1) Определить число = k (2) Используйте рекурсивный обход до конца связанного списка. (3) Возврат с конца и уменьшение num на 1 каждый раз, когда он возвращается (4) Когда число равно 0, целевой узел может быть найден
2.3.2 Графический процесс
2.3.3 Реализация кода
int num;//定义num值
ListNode* findKthTail(ListNode* pHead, int k) {
num = k;
if(pHead == NULL)
return NULL;
//递归调用
ListNode* pCur = findKthTail(pHead->next, k);
if(pCur != NULL)
return pCur;
else{
num--;// 递归返回一次，num值减1
if(num == 0)
return pHead;//返回倒数第K个节点
return NULL;
}
}
Рекурсивному методу по-прежнему необходимо дважды пройти по связанному списку, а временная сложность составляет O (n * 2).
2.4 Метод двойного указателя
2.4.1 Идеи решения проблем
(1) Определите два указателя p1 и p2, чтобы они указывали на головной узел связанного списка соответственно. (2) p1 продвигается вперед на K узлов, тогда p1 и p2 удаляются на K узлов. (3) p1 и p2 продвигаются одновременно, по одному узлу за раз. (4) Когда p1 указывает на конец связанного списка, поскольку p1 и p2 отстоят друг от друга на K узлов, p2 указывает на целевой узел.
2.4.2 Графический процесс
2.4.3 Реализация кода
ListNode* findKthTail(ListNode *pHead, int K){
if (NULL == pHead || K == 0)
return NULL;
//p1，p2均指向头节点
ListNode *p1 = pHead;
ListNode *p2 = pHead;
//p1先出发，前进K个节点
for (int i = 0; i < K; i++) {
if (p1)//防止k大于链表节点的个数
p1 = p1->_next;
else
return NULL;
}
while (p1)//如果p1没有到达链表结尾，则p1，p2继续遍历
{
p1 = p1->_next;
p2 = p2->_next;
}
return p2;//当p1到达末尾时，p2正好指向倒数第K个节点
}
Видно, что при использовании метода двойного указателя нужно пройти по связному списку только один раз.Этот метод более эффективен, а временная сложность O (n).Обычно этот метод также тестируется в письменных тестовых вопросах.
3 Проблема с кольцом в связанном списке
3.1 Определить, есть ли цикл в связном списке
Кольцо в односвязном списке означает, что следующий указатель узла в конце связанного списка не равен NULL, а указывает на узел в связанном списке, что приводит к кольцевой структуре в связанном списке.
Схематическая диаграмма цикла в связанном списке:
Узел 8 в конце связанного списка указывает на узел 3 в связанном списке, что приводит к кольцевой структуре связанного списка. Какими методами можно определить, является ли связный список циклическим?
3.1.1 Метод исчерпывающего сравнения
3.1.1.1 Идеи решения проблем
(1) Пройдите по связанному списку и запишите посещенные узлы. (2) Сравните текущий узел с предыдущим и посещенным узлами, если есть тот же узел, есть кольцо. Иначе кольца нет.
Этот вид исчерпывающего сравнения прост в идее, но эффективность слишком низка, особенно когда количество узлов связанного списка велико, сравнение занимает много времени, а временная сложность составляет примерно O(n^2). Этот метод, естественно, не является идеальным ответом для спрашивающего. Если вы используете этот метод в письменном тестовом интервью, предполагается, что вы встанете на колени.Забудьте об этом методе.
3.1.2 Метод кэширования хэшей
Поскольку процесс сравнения элементов занимает много времени при исчерпывающем обходе, есть ли способ улучшить скорость сравнения?
3.1.2.1 Идеи решения проблем
(1) Сначала создайте коллекцию HashSet с идентификатором узла в качестве ключа для хранения пройденных узлов. (2) Начиная с головного узла, пройти по очереди каждый узел односвязного списка. (3) Каждый раз, когда просматривается новый узел, новый узел сравнивается с узлом, хранящимся в коллекции HashSet.Если в HashSet обнаружен тот же идентификатор узла, это означает, что связанный список имеет кольцо.Если тот же узел ID не существует в HashSet, затем сохраните этот новый ID узла в HashSet, затем введите следующий узел и продолжайте повторять операцию прямо сейчас.
Предположим, что расстояние от головного узла связанного списка до точки входа равно a, а длина кольца связанного списка равна r. Временная сложность каждого элемента поиска HashSet равна O(1), поэтому общая временная сложность равна1 * ( a + r ) = a + r, что можно просто понимать как O (n). Пространственная сложность алгоритма по-прежнему равна a + r - 1, что можно просто понять как O (n).
3.1.3 Метод быстрого и медленного указателя
3.1.3.1 Идеи решения проблем
(1) Определите два указателя как медленные и быстрые соответственно и укажите указатели на головной узел связанного списка. (2) Предусмотрено, что медленный указатель перемещается каждый раз на один узел, а быстрый указатель каждый раз перемещается на два узла. (3) Когда медленное и быстрое равны, и ни одно из них не пусто, в связанном списке есть цикл.
3.1.3.2 Графический процесс
Ациклический процесс:
Из графического процесса видно, что если в списке нет кольца, быстрый и медленный указатели могут встретиться только в конце связанного списка.
Циклический процесс:
Из графического процесса видно, что если в связном списке есть кольцо, то быстрый и медленный указатели должны встретиться в кольце. Это похоже на гонки черепахи и зайца по круговой дорожке. Поскольку скорость кролика больше скорости черепахи, кролик и черепаха снова встретятся. Поэтому, когда быстрый и медленный указатели равны, и они не равны NULL, это указывает на наличие цикла в связанном списке.
3.1.3.3 Реализация кода
bool isExistLoop(ListNode* pHead) {
ListNode* fast;//慢指针，每次前进一个节点
ListNode* slow;//快指针，每次前进2个节点
slow = fast = pHead ; //两个指针均指向链表头节点
//当没有到达链表结尾，则继续前进
while (slow != NULL && fast -> next != NULL) {
slow = slow -> next ; //慢指针前进一个节点
fast = fast -> next -> next ; //快指针前进两个节点
if (slow == fast) //若两个指针相遇，且均不为NULL则存在环
return true ;
}
//到达末尾仍然没有相遇，则不存在环
return false ;
}
3.2 Ввод установочного кольца
В разделе 3.1 реализован метод определения наличия цикла в связанном списке. Тогда, когда в связанном списке есть кольцо, как определить входной узел кольца?
3.2.1 Идеи решения проблем
Медленный указатель перемещается по одному узлу за раз, поэтому, когда медленный встречается с быстрым, медленный не проходит весь связанный список. Пусть количество узлов, через которые проходят медленные, равно s, а количество узлов, через которые проходят быстрые, равно 2s. Пусть расстояние от точки входа кольца до головного узла равно a, расстояние от первой точки встречи медленного и быстрого до точки входа равно b, а длина кольца равна r. Тогда есть: с = а + б; 2s = n * r + a + b; n представляет количество раз, которое быстрый указатель прошел по кольцу. затем запускает: s = n * r означает, что длина медленного указателя кратна длине кольца.
Если степень от головного узла связанного списка до конечного узла кольца равна L, расстояние между узлами встречи медленного и быстрого равно X от входного узла кольца. Тогда есть: а + X = s = n * r = (n - 1) * r + (L - a); а = (n - 1) * r + (L - а - X); Из приведенного выше уравнения видно, что: Запускаем указатель p1 из точки, где встречаются медленная и быстрая, и идем на (L - a - X) шагов, после чего этот указатель достигает узла входа. В то же время указатель p2 начинается с головного узла и продвигается на шаг вперед. Когда точки p1 и p2 встречаются, обе точки p1 и p2 указывают на узел входа.
Например, связанный список, показанный на рис. 3.1: медленное прохождение узла s = 6; быстрые обходы узла 2s = 12; Головной узел потока данных узла входа кольца a = 3; Расстояние от места встречи до головного узла Х = 3; Л = 8; г = 6; Можно сделать вывод, что верно a = (n - 1) * r + (L - a - X).
3.2.2 Графический процесс
3.2.3 Реализация кода
//找到环中的相遇节点
ListNode* getMeetingNode(ListNode* pHead) // 假设为带头节点的单链表
{
ListNode* fast;//慢指针，每次前进一个节点
ListNode* slow;//快指针，每次前进2个节点
slow = fast = pHead ; //两个指针均指向链表头节点
//当没有到达链表结尾，则继续前进
while (slow != NULL && fast -> next != NULL){
slow = slow -> next ; //慢指针前进一个节点
fast = fast -> next -> next ; //快指针前进两个节点
if (slow == fast) //若两个指针相遇，且均不为NULL则存在环
return slow;
}
//到达末尾仍然没有相遇，则不存在环
return NULL ;
}
//找出环的入口节点
ListNode* getEntryNodeOfLoop(ListNode* pHead){
ListNode* meetingNode = getMeetingNode(pHead); // 先找出环中的相遇节点
if (meetingNode == NULL)
return NULL;
ListNode* p1 = meetingNode;
ListNode* p2 = pHead;
while (p1 != p2) // p1和p2以相同的速度向前移动，当p2指向环的入口节点时，p1已经围绕着环走了n圈又回到了入口节点。
{
p1 = p1->next;
p2 = p2->next;
}
//返回入口节点
return p1;
}
3.3 Расчет длины кольца
3.3.1 Идеи решения проблем
В 3.1 найден узел встречи между медленным и быстрым, а указатели solw и fast начинаются с узла встречи.Согласно предыдущему прямому правилу, когда медленные и быстрые снова встречаются, длина медленных перемещений точно равна длине пути. звенеть.
3.3.2 Графический процесс
3.3.3 Реализация кода
int getLoopLength(ListNode* head){
ListNode* slow = head;
ListNode* fast = head;
while ( fast && fast->next ){
slow = slow->next;
fast = fast->next->next;
if ( slow == fast )//第一次相遇
break;
}
//slow与fast继续前进
slow = slow->next;
fast = fast->next->next;
int length = 1; //环长度
while ( fast != slow )//再次相遇
{
slow = slow->next;
fast = fast->next->next;
length ++; //累加
}
//当slow与fast再次相遇，得到环长度
return length;
}
4 Добавление больших чисел с помощью связанных списков
4.1 Описание проблемы
Два целых числа, представленные в виде связанного списка, где каждый узел содержит число. Числа хранятся в порядке, обратном исходным целым числам, так что первое число находится в начале списка. Напишите функцию, которая складывает два целых числа и возвращает сумму в виде связанного списка.
Например: входить: 3->1->5->ноль 5->9->2->ноль, вывод: 8->0->8->ноль
4.2 Реализация кода
ListNode* numberAddAsList(ListNode* l1, ListNode* l2) {
ListNode *ret = l1, *pre = l1;
int up = 0;
while (l1 != NULL && l2 != NULL) {
//数值相加
l1->val = l1->val + l2->val + up;
//计算是否有进位
up = l1->val / 10;
//保留计算结果的个位
l1->val %= 10;
//记录当前节点位置
pre = l1;
//同时向后移位
l1 = l1->next;
l2 = l2->next;
}
//若l1到达末尾，说明l1长度小于l2
if (l1 == NULL)
//pre->next指向l2的当前位置
pre->next = l2;
//l1指针指向l2节点当前位置
l1 = pre->next;
//继续计算剩余节点
while (l1 != NULL) {
l1->val = l1->val + up;
up = l1->val / 10;
l1->val %= 10;
pre = l1;
l1 = l1->next;
}
//最高位计算有进位，则新建一个节点保留最高位
if (up != 0) {
ListNode *tmp = new ListNode(up);
pre->next = tmp;
}
//返回计算结果链表
return ret;
}
5 Слияние упорядоченного связанного списка
5.1 Описание проблемы
Вопрос: объединить два отсортированных связанных списка в новый отсортированный связанный список и вернуться. Новый связанный список формируется путем соединения всех узлов данных двух связанных списков.
Пример: входить: 1->2->4, 1->3->4 вывод: 1->1->2->3->4->4
5.2 Поток алгоритма
5.3 Общая схема
5.3.1 Идеи решения проблем
(1) Обработать наличие пустого связанного списка.Если pHead1 пуст, вернуть pHead2, а если pHead2 пуст, вернуть pHead1. (Оба пусты, эта ситуация была перехвачена, когда pHead1 пуст) (2) Определите первый узел, когда два связанных списка не имеют пустого связанного списка, сравните значение первого узла связанного списка 1 и связанного списка 2 и сохраните узел с меньшим значением в качестве первого объединенного узла. И переместите связанный список, первый узел которого является наименьшим элементом назад. (3) Продолжайте выбирать небольшое значение в оставшихся элементах, подключайтесь к задней части первого узла и продолжайте подключать следующий узел с небольшим значением к задней части первого узла, пока определенный связанный список не станет пустым. (4) Когда длины двух связанных списков несовместимы, то есть один из связанных списков пуст после завершения сравнения, в это время необходимо соединить оставшиеся элементы другого связанного списка с обратной стороной. первого узла.
5.3.2 Реализация кода
ListNode* mergeTwoOrderedLists(ListNode* pHead1, ListNode* pHead2){
ListNode* pTail = NULL;//指向新链表的最后一个结点 pTail->next去连接
ListNode* newHead = NULL;//指向合并后链表第一个结点
if (NULL == pHead1){
return pHead2;
}else if(NULL == pHead2){
return pHead1;
}else{
//确定头指针
if ( pHead1->data < pHead2->data){
newHead = pHead1;
pHead1 = pHead1->next;//指向链表的第二个结点
}else{
newHead = pHead2;
pHead2 = pHead2->next;
}
pTail = newHead;//指向第一个结点
while ( pHead1 && pHead2) {
if ( pHead1->data <= pHead2->data ){
pTail->next = pHead1;
pHead1 = pHead1->next;
}else {
pTail->next = pHead2;
pHead2 = pHead2->next;
}
pTail = pTail->next;
}
if(NULL == pHead1){
pTail->next = pHead2;
}else if(NULL == pHead2){
pTail->next = pHead1;
}
return newHead;
}
5.4 Рекурсивная схема
5.4.1 Идеи решения проблем
(1) Обработать наличие пустого связанного списка.Если pHead1 пуст, вернуть pHead2, а если pHead2 пуст, вернуть pHead1. (2) Сравните размер первого узла двух связанных списков и определите позицию головного узла. (3) После того, как головной узел определен, продолжайте выбирать следующий узел среди оставшихся узлов, чтобы связать его с узлом, выбранным на втором шаге, а затем продолжайте повторять шаги (2) (3), пока не появится связанный список. пусто.
5.4.2 Реализация кода
ListNode* mergeTwoOrderedLists(ListNode* pHead1, ListNode* pHead2){
ListNode* newHead = NULL;
if (NULL == pHead1){
return pHead2;
}else if(NULL ==pHead2){
return pHead2;
}else{
if (pHead1->data < pHead2->data){
newHead = pHead1;
newHead->next = mergeTwoOrderedLists(pHead1->next, pHead2);
}else{
newHead = pHead2;
newHead->next = mergeTwoOrderedLists(pHead1, pHead2->next);
}
return newHead;
}
}
6 Удалить узел в связанном списке, временная сложность должна быть O(1)
6.1 Описание проблемы
Дана голова в односвязном списке и узел, ожидающий удаления. Удалите узел связанного списка с временной сложностью O(1). А после удаления узла вернуться в шапку.
Пример: Учитывая 1->2->3->4 и узел 3, вернуть 1->2->4.
6.2 Идеи решения проблем
В представленном ранее односвязном списке для удаления узлов наиболее распространенным методом является обход связанного списка, а сложность — O(n). Если мы присвоим удаляемому узлу значение следующего узла удаляемого узла, а затем удалим этот узел, это эквивалентно удалению узла, который необходимо удалить. Поскольку мы можем легко добраться до следующего узла удаленного узла, сложность должна быть только O (1).
Пример Односвязный список: 1->2->3->4->NULL Чтобы удалить узел 3 . Первый шаг присваивает значение 4 следующего узла узла 3 текущему узлу. Он становится 1->2->4->4->NULL, а затем удалите узел 4 для достижения цели. 1->2->4->НОЛЬ
Если удаленный узел является головным узлом, установите головной узел в NULL. Если удаленный узел является хвостовым узлом, его можно пройти только от начала к предыдущему узлу головного узла.
6.3 Графический процесс
6.4 Реализация кода
void deleteNode(ListNode **pHead, ListNode* pDelNode) {
if(pDelNode == NULL)
return;
if(pDelNode->next != NULL){
ListNode *pNext = pDelNode->next;
//下一个节点值赋给待删除节点
pDelNode->val = pNext->val;
//待删除节点指针指后面第二个节点
pDelNode->next = pNext->next;
//删除待删除节点的下一个节点
delete pNext;
pNext = NULL;
}else if(*pHead == pDelNode)//删除的节点是头节点
{
delete pDelNode;
pDelNode= NULL;
*pHead = NULL;
} else//删除的是尾节点
{
ListNode *pNode = *pHead;
while(pNode->next != pDelNode) {
pNode = pNode->next;
}
pNode->next = NULL;
delete pDelNode;
pDelNode= NULL;
}
}
7 Распечатайте связанный список от начала до конца
7.1 Описание проблемы
Введите связанный список и верните ArrayList в порядке значений связанного списка от конца до конца.
7.2 Решение
На первый взгляд, смысл заголовка в том, что при выводе элементы в конце связанного списка помещаются на передний план, а элементы в начале связанного списка — на задний. Разве это неФИФО, ЛИФОКакие.
Какая структура данных соответствует этому требованию?
куча!
7.2.1 Реализация кода
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> value;
ListNode *p=NULL;
p=head;
stack<int> stk;
while(p!=NULL){
stk.push(p->val);
p=p->next;
}
while(!stk.empty()){
value.push_back(stk.top());
stk.pop();
}
return value;
}
};
7.3 Решение 2
Второй метод также относительно прост: при построении связанного списка, если сохраняется последний узел, оставшийся метод обработки связанного списка остается неизменным, поэтому его можно обрабатывать в рекурсивной форме.
7.3.1 Реализация кода
class Solution {
public:
vector<int> value;
vector<int> printListFromTailToHead(ListNode* head) {
ListNode *p=NULL;
p=head;
if(p!=NULL){
if(p->next!=NULL){
printListFromTailToHead(p->next);
}
value.push_back(p->val);
}
return value;
}
};
8 Обратно связанный список
8.1 Описание темы
Обратить односвязный список.
Пример:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
Передовой:Вы можете реверсировать связанный список итеративно или рекурсивно. Можно ли решить эту задачу двумя способами?
8.2 Идеи решения проблем
Настройте три узлаpre,cur,next
- (1) Просмотр каждый раз
curявляется ли узелNULL, если да, завершаем цикл и получаем результат - (2) если
curузел не дляNULL, затем сначала установите временную переменнуюnextзаcurследующий узел - (3) пусть
curСледующий узел становится указывает наpre,тогдаpreпереехатьcur,curперейти кnext - (4) Повторить (1) (2) (3)
анимация
8.3 Реализация кода
8.3.1 Метод итерации
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = NULL;
ListNode* cur = head;
while(cur != NULL){
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
};
8.3.2 Рекурсивная обработка
class Solution {
public:
ListNode* reverseList(ListNode* head) {
// 递归终止条件
if(head == NULL || head->next == NULL)
return head;
ListNode* rhead = reverseList(head->next);
// head->next此刻指向head后面的链表的尾节点
// head->next->next = head把head节点放在了尾部
head->next->next = head;
head->next = NULL;
return rhead;
}
};
End
Количество лайков у статьи в последнее время немного меньше.Если статья была вам полезна, ставьте лайк~