链表

依照视频的思路,过一段时间再去leetcode验证

预备知识: 链表基础

#include <iostream>

namespace LinkedList {
    struct ListNode {
        int val{0}; // 存储元素的数据域
        ListNode *next{nullptr}; // 存储下一个节点地址的指针域
        // 这部分原题目估计有问题
    };

    void learn00::testPrint() {
        // 尝试测试链表
        // 创建五个节点
        ListNode a;
        ListNode b;
        ListNode c;
        ListNode d;
        ListNode e;

        a.val = 10;
        b.val = 20;
        c.val = 30;
        d.val = 40;
        e.val = 50;

        // 连接节点
        a.next = &b;
        b.next = &c;
        c.next = &d;
        d.next = &e;

        ListNode *head = &a;
        while(head) {
                std::cout << head->val << std::endl;
                head = head->next;
            }

    }
}

链表的创建

基本形式:

struct ListNode {
    int val; // 存储元素的数据域
    ListNode *next; // 存储下一个节点地址的指针域
};

一些思考

但值得注意的是,如果按照开头的代码处理链表节点的话,next指针域会随机赋给予初值,此时的地址只想会如下图:

根据上述链表定义创建的链表后地址

由于ListNode是一个结构体,在C++中与class是基本上无异的。ListNode *next是一个指向ListNode类型的指针,那么编译器将会对next初始化,而我们没有定义初始化的变量是什么,就可能会赋值到随机指针,造成了上述的问题。但具体的变化流程是怎么样的呢?我们再尝试下:

int main() {
    ListNode a; // 单独创建一个节点
    return 0;
}

它产生的结果:

ListNode a

十分奇怪!那改成一个ListNode *a

这样也懵了,两者为何不相同呢?

我们一步一步来分析:

ListNode a;
// 0 此时a 是一个 ListNode类型的变量
// 1 而a中有一个 ListNode 的指针 next
// 2 我们在初始化a时没有赋予其一个规定的初值 因而 next也会初始化自己
// 3 因而 next 是指向一个ListNode的 指针,编译器需要找一个ListNode类型的值,并找到它的地址
// 4 实际上我们并没有手动创造这么一样定义,于是编译器会去尝试去初始化next
// 5 而next的指向的地址依旧需要一个 next 指针,编译器会再尝试去初始化

ListNode *a;
// 按照上述分析,而我们对比,可以看到指针的ListNode初始化的层数比上述的少一层

再者,先推断,编译器会尝试初始化两层指针(next)。我们整个ListNode **a

编译器很无力。

而前面我们还注意到一些问题,在声明多个变量的时候,出了些问题,第一个变量默认值为0,地址也为nullptr

ListNode a;
ListNode b;
ListNode c;

多个变量的情况

很明显,这个情况不可复现!

没有找到相关的资料,这也是奇怪的现象。可能是C++编译器的问题,于是乎我尝试写了下C的版本,得到下面的结果:

C的结果

很明显,struct结构体的定义就是错误的,如果没有给予编译器明确的指令,明显会出问题!定义链表时,未定义的行为可能是程序崩溃的重要原因。要注意并杜绝这类的行为(主要视频中给出的是这么简陋的定义,尝试分析了下),因而正常应当在结构体中赋予变量初值,next指向nullptr(这也是链表在书面上的定义与要求)。

C中还需要写一个函数进行初始化操作:

void InitListNode(ListNode * List) {
    List->val = 0;
    List->next = NULL;
}

// 那编译器自动创建的地址怎么办?

C++struct就是class(细节上有区别),可以直接实现初始化:

struct ListNode {
    int val{0}; // 存储元素的数据域
    ListNode *next{nullptr}; // 存储下一个节点地址的指针域
        // 这部分原题目估计有问题
};

一般的,初始化在构造函数中实现:

struct ListNode {
    int val; // 存储元素的数据域
    ListNode *next; // 存储下一个节点地址的指针域
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}

    // 这部分原题目估计有问题
};

正确状态

链表的逆置

基本思路已经写入代码注释

v1. 直接反转链表

-> leetcode-反转链表

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
   /**
   依次遍历链表节点,每遍历一个节点即逆指一个节点
   1. 备份 head->next
   2. 修改 head->next
   3. 移动 head 与 new_head
  */
    ListNode* reverseList(ListNode* head) {
        ListNode* new_head = nullptr;
        ListNode* tmp = head;

        while (tmp) {
            // 1. 备份 head->next
            ListNode* next = tmp->next;
            // 2. 修改 head->next
            tmp->next = new_head;
            // 3. 移动 head 与 new_head
            new_head = tmp;
            tmp = next;
        }
        return new_head;
    }
};

v2. 反转从m到n的链表

-> leetcode-反转链表2

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
// 链表 从 m 逆置到 n
ListNode* reverseBetween(ListNode *head, int m, int n) {
    // 1. 计算需要逆置的节点个数
    int chang_len = n - m + 1;
    // 2. 初始化开始逆置节点的前驱
    ListNode *pre_head = nullptr;
    // 3. 最终转换后的链表头节点,非特殊情况即为head
    ListNode *result = head;
    while (head && --m) {
        // 4. 将 head 向前移动 m-1 个位置
        // 记录head的前驱
        pre_head = head;
        head = head->next;
    }

    // 5. 将 modify_list_tail 指向当前的 head,即逆置后的链表尾
    ListNode *modify_list_tail = head;
    ListNode *new_head = nullptr;

    // 6逆置 change_len 个节点
    while (head && chang_len) {
        // 同 链表逆置1的方法
        ListNode *next = head->next;
        head->next = new_head;
        new_head = head;
        head = next;

        // 完成一个节点逆置
        --chang_len;
    }
    // 7 连接 尾节点
    // 连接逆置后链表尾与逆置段的后一个节点
    modify_list_tail->next = head;

    // 8 如果 pre_head不空,说明不是从第一个节点开始逆置的 m>1
    // 连接头节点
    if (pre_head) {
        // 不是第一个节点逆置
        pre_head->next = new_head;
    } else {
        // 直接赋值
        // 如果pre_head 为空 说明 m==1 从第一个节点开始逆置 结果为逆置后的头节点
        result = new_head;
    }

    return result;
}

求两个链表的交点

-> leetcode-链表的交点

法1: set的使用

ListNode* getIntersectionNode(ListNode *headA, ListNode *headB) {
    std::set<ListNode *> node_set;
    // 1. 遍历遍表A
    while(headA) {
        node_set.insert(headA);
        headA = headA->next;
    }

    // 2. 在b中查找该节点
    while(headB) {
        if (node_set.find(headB) != node_set.end()) {
            return headB;
        }
        headB = headB->next;
    }

    return nullptr;
}

set 查找的时间复杂度 O(nlogn),而查找 headB 最差时间复杂度是 O(n) 。空间复杂度 O(n) 。不符合题意。

法2: 先同步链表再查找

// 获取链表长度 O(n)
int get_list_length(ListNode* head) {
    int len{0};
    while (head) {
        ++len;
        head = head->next;
    }

    return len;
}

// 同步 O(m-n)
ListNode * forward_long_list(int long_len, int short_len, ListNode *head) {
    // 同步
    int delta{long_len - short_len};

    while (head && delta) {
        head = head->next;
        --delta;
    }

    return head;
}

// 时间 O(n)
// 空间 O(1)
ListNode * getIntersectionNode(ListNode *headA, ListNode *headB) {
    int list_A_len = get_list_length(headA);
    int list_B_len = get_list_length(headB);

    if (list_A_len > list_B_len) {
        headA = forward_long_list(list_A_len, list_B_len, headA);
    } else {
        headB = forward_long_list(list_B_len, list_A_len, headB);
    }

    // 遍历两个链表
    while (headA && headB) {
        if (headA == headB) {
            return headA;
        }
        headA = headA->next;
        headB = headB->next;
    }

    return nullptr;
}

此时明显空间复杂度在 O(1) ,而时间复杂度 为 O(n)

链表求环

-> leetcode-链表求环

法1: 利用set

  1. 遍历链表,将链表中的节点对应的地址插入 set 中;
  2. 在遍历时插入节点前,在 set 中查找, 第一个在 set 中发现的节点地址,即是链表的起点
// 时间复杂度 O(n) 空间复杂度 O(n)
ListNode *detectCycle(ListNode *head) {
    std::set<ListNode *> node_set;
    while (head) {
        // 查找是否曾经存入节点
        if (node_set.find(head) != node_set.end()) {
            return head;
        }
        node_set.insert(head);
        head = head->next;
    }

    return nullptr;
}

法2: 快慢指针赛跑

设两个指针,一个快指针fast,一个慢指针slow

​ - -

1 => 2 => 3(环节点) => 4 => 5 => 6 => 3(环节点)

  1. *slow: 2 ; *fast: 2 3
  2. *slow: 2 3 ; *fast: 2 3 4 5
  3. *slow: 2 3 4 ; *fast: 2 3 4 5 6 3
  4. *slow: 2 3 4 5 ; *fast: 2 3 4 5 6 3 4 5;

依照上述过程,fast 总会和 slow 相遇,而此时我们没有完成查找,只是确定了该链表有环,接下来需要对这个过程分析:

  1. *fast 遍历过的节点总是 *slow 遍历的节点的两倍;
  2. 当两者相遇的时候,必定经历了环节点的起始节点;
  3. 定义: a: 1 2 3; b: 4 5; c: 6
  4. 则 fast = a + b + c + b, slow = a + b
  5. a + b + c = 2(a + b)
  6. 则 a = c; 从而可以推断*head到环起始节点 和 相遇节点到环起始节点相差的节点数一样
  7. 定义该相遇节点下一个节点为 *meet,接下来移动 *head:
    1. *meet: 5 ; *head: 1
    2. *meet: 6 ; *head: 2
    3. *meet: 3 ; *head: 3

代码实现:

ListNode *detectCycle(ListNode *head) {
    // 快指针
    ListNode *fast = head;
    // 慢指针
    ListNode *slow = head;
    // 相遇节点
    ListNode *meet = nullptr;

    // 移动节点
    while (fast) {
        // 同时走一步
        fast = fast->next;
        slow = slow->next;
        // fast 是 nullptr 弹出
        if (!fast) {
            break;
        }

        // fast 快一步
        fast = fast->next;
        // 如果 fast == slow
        if (fast == slow) {
            meet = fast;
            break;
        }
    }

    // 获得 meet 节点
    // 如果 meet nullptr 则不成为环
    if (!meet) {
        return nullptr;
    }

    // 此时 包含meet节点
    while (head && meet) {
        if (head == meet) {
            return head;
        }
        head = head->next;
        meet = meet->next;
    }

    // 空
    return nullptr;
}

链表划分

-> leetcode -- 分隔链表

  1. 建立两个临时节点,一个 *less_head,一个 *more_head;
  2. 遍历链表,当遇到 < 时 存入 *less_head ; 当遇到 >= 时 存入 *more_head;
  3. *less_head -> ... -> *more_head -> ... -> *nullptr 完成连接
ListNode* partition(ListNode* head, int x) {
    // 两个临时头节点
    ListNode less_head(0);
    ListNode more_head(0);
    ListNode *less_ptr = &less_head;
    ListNode *more_ptr = &more_head;

    while (head) {
        // 如果节点小于x,则将节点插入less_ptr中
        if (head->val < x) {
            less_ptr->next = head;
            less_ptr = head;
        } else {
            // 如果节点大于等于x,则存入more_ptr中
            more_ptr->next = head;
            more_ptr = head;
        }
        // 继续遍历
        head = head->next;
    }

    // 将 less 连接到尾部  more_head 头部
    less_ptr->next = more_head.next;
    // more 接 nullptr
    more_ptr->next = nullptr;

    // 已经存储头节点
    return less_head.next;
}

时间复杂度O(n)

复杂的链表的深度拷贝

-> leetcode -- 复制带随机指针的链表

该题目的难点在于如何记录 random 指向的节点,如果记录了 random 指向的节点,就可以照常实现链表的深度拷贝。

预备的知识:map

使用 map 可以存储节点地址与节点序号对应。

#include <iostream>
#include <map>

using namespace std;

class Node {
public:
    int label;
    Node *next, *random;
    Node(int x): label(x), next(nullptr), random(nullptr){}
};

int main()
{
    // 设置一个节点map, key 为 节点的地址 , value 为整型 --> 唯一 id 值
    std::map<Node *, int> node_map;
    Node a(5), b(3), c(6);
    a.next = &b;
    b.next = &c;

    a.random = &c;
    b.random = &a;
    c.random = &c;

    node_map[&a] = 1;
    node_map[&b] = 2;
    node_map[&c] = 3;

    cout << "a.random id = " << node_map[a.random] << endl;
    cout << "b.random id = " << node_map[b.random] << endl;
    cout << "c.random id = " << node_map[c.random] << endl;
    return 0;
}

使用 map 解决该问题

使用两个 map,对于旧链表,存储其节点地址并标注序号;对于新链表,存储其序号并标注其节点地址:

Node* copyRandomList(Node* head) {
    if (!head) {
        return head;
    }

    // 地址到节点位置的map
    std::unordered_map<Node*, int> old_nodes;
    // 使用 vector 根据存储节点位置访问地址
    // 也可以使用 map  unordered_map<int, Node*>
    // vector 可以直接使用push_back替代该功能
    std::vector<Node *> new_nodes;

    Node * ptr = head;
    int index{0};

    // 遍历原始列表
    while (ptr) {
        // 将新链表的节点push入new_nodes中
        new_nodes.push_back(new Node(ptr->val));
        old_nodes[ptr] = index;

        ptr = ptr->next;
        ++index;
    }

    // 保证最后一个节点 后续无需多加判断
    new_nodes.push_back(nullptr);

    ptr = head;
    index = 0;
    // 再次遍历 写入
    while (ptr) {
        new_nodes[index]->next = new_nodes[index + 1];
        if (ptr->random) {
            // 找到 random 的地址对应的id
            int id = old_nodes[ptr->random];
            // 拷贝对应的 id 指向
            new_nodes[index]->random = new_nodes[id];
        }

        ptr = ptr->next;
        ++index;
    }

    return new_nodes[0];
}

时间复杂度 O(n) ,使用 两个 map 存储了数据,空间复杂度 O(n)

排序链表的合并

v1: 两个排序链表的合并

-> leetcode -- 合并两个有序列表

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    // 设置临时头节点
    ListNode temp_head(0);
    // 使用 pre 指针指向 temp_head
    ListNode *pre = &temp_head;

    while (l1 && l2) {
        // 获取较小的部分
        if (l1->val < l2->val) {
            // pre->next 指向小的部分
            pre->next = l1;
            // 往下遍历
            l1 = l1->next;
        } else {
            pre->next = l2;
            l2 = l2->next;
        }
        // 移动指针
        pre = pre->next;
    }

    // 其中一个链表剩余则接下来的节点都是有序的
    if (l1) {
        pre->next = l1;
    }
    if (l2) {
        pre->next = l2;
    }

    // temp_head 所在的地址的 next 指向头节点
    return temp_head.next;
}

时间复杂度 O(min(m, n)) , m n 分别是 l1 l2 的长度。

v2. 多个排序链表的合并

-> leetcode -- 合并k个升序链表

法1: 暴力合并

参考两个链表的合并,遍历 k 个链表,依次按照两个链表连接的方法连接。连接一个之后存储一个结果中,供下一个连接过程使用。

法2: 排序后遍历

所有节点存入 vector 中,再将 vector 排序,再将节点顺序相连。

时间复杂度 O(kN*logkN)

// 排序
static bool cmp(const ListNode *a, const ListNode *b) {
    return a->val < b->val;
}

ListNode* mergeKLists(vector<ListNode*>& lists) {
    // 排序法
    std::vector<ListNode *> node_vec;
    for (auto *node : lists) {
        ListNode *tmp = node;
        while (tmp) {
            node_vec.push_back(tmp);
            tmp = tmp->next;
        }
    }

    // 如果没有链表
    if (0 == node_vec.size()) {
        return nullptr;
    } 

    // 根据节点的值执行排序
    std::sort(node_vec.begin(), node_vec.end(), cmp);
    // 连接
    for (int i{0}; i<node_vec.size()-1; ++i) {
        node_vec[i]->next = node_vec[i+1];
    }

    node_vec[node_vec.size()-1]->next = nullptr;


    return node_vec[0];
}

法3: 分治后相连

对 k 个链表进行分治,两两进行合并。

时间复杂度 O(kNlogk)

ListNode* mergeKLists(vector<ListNode*>& lists) {
     // 分治
     if (0 == lists.size()) {
         return nullptr;
     }
     if (1 == lists.size()) {
         return lists[0];
     }
     if (2 == lists.size()) {
         return mergeTwoLists(lists[0], lists[1]);
     }

     // 开始分治
     int mid = lists.size() / 2;

     std::vector<ListNode *> sub1_lists;
     std::vector<ListNode *> sub2_lists;
     for (int i{0}; i < mid; ++i) {
         sub1_lists.push_back(lists[i]);
     }
     for (int i{mid}; i < lists.size(); ++i) {
         sub2_lists.push_back(lists[i]);
     }
     ListNode *l1 = mergeKLists(sub1_lists);
     ListNode *l2 = mergeKLists(sub2_lists);

     return mergeTwoLists(l1, l2); 
 }

相对排序法,实际运行时间更长(可能机器有优化)。

总结

链表中单链是最简单的,在这么多的题目当中,也是单链的题目最多,而环链为辅助,基本不存在双向链表的题目。

设计链表当中为了提高增删效率,可以自己设计一个双向链表。

链表的头

在数据结构的学习当中,可以清晰的认识到链表的头指针为空(非需要的数据)操作的时候会相当方便,在操作实用数据中,置换头节点不需要考虑特殊情况,只需按照设计好的方法直接执行即可等等。

题目中多数头节点非空,我们可以自己手动第一这个空头节点,方便后面的操作:

ListNode p_head(-1);
p_head.next = head;
ListNode *pre = &p_head;

// 此时 pre->next 指向 head

双指针

链表题目当中,比较普遍的解法是使用 双指针法,也可以当成是多指针法。

首先普通的双指针法,可能是预留当前指针的前一个节点,在删除当前节点时候十分有效,需要分析需求确定是否需要前置节点。

其次是快慢指针,中等难度的题目基本上可以用得上快慢指针,最常见的是可以确定单链的中部:

fast = fast->next->next;
slow = slow->next;

// fast 永远走两步, slow 走一步
// 当 fast 走到中点的时候,slow刚刚好就在中间

有效的组合应用多指针,可以解决不少问题,慢指针负责记忆,而快指针负责向前探索,想想就效率高。

队列与栈的结合

队列和栈可以独立成一个板块,但 C++ 标准库内置这些数据结构,我们可以借助两者的特性解决链表的问题,如链表的逆置、判断回文等等。

如何组合还是要实质分析,解答完全可以尝试使用其他数据结构的特性实现的。当然,如果能够直接解答,肯定是直接解答分高。

综合方法

难度较大的题目会综合多种方法,而有时候也会出现一些数据结构之外的题目,可能也会有数学相关的问题,不过不难,都可以理解。

链表类的题目都好理解,如果出现了无法理解的题目,那肯定是出题的人不会组织语言,不做的就完事了,这两天碰到几道题目,测试的时候答案都是错误的,但提交能够通过,而且题意和测试用例根本对不上。

做几道质量高的题目并搞懂就过关了,傻乎乎做完全部题目,现在这个情况不太显示。