链表.md

• 链表理论基础
• 链表中常见的面试题型
• 链表题型
  • leetcode.707 设计链表
  • leetcode.24 两两交换链表中的节点
  • leetcode.237 删除链表中的节点
  • leetcode.19 删除链表的倒数第 N 个结点
  • leetcode.61 旋转链表
  • leetcode.143 重排链表
  • leetcode.138 复制带随机指针的链表

---

链表理论基础

1. 链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向 $null$（空指针的意思），链表的入口节点称为链表的头结点也就是 $head$
2. 链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理
3. 由于链表的内存不是连续分布的，所以比较方便进行增加和删除，不方便查询
4. 链表的定义

// 单链表
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
}*head;

链表中常见的面试题型

1. 设计链表
2. 链表的基本性质解题
3. 双指针算法（见双指针算法总结）
4. 合并链表（归并排序）

链表题型

leetcode.707 设计链表

• 链接https://leetcode.cn/problems/design-linked-list/
• leetcode解题代码

class MyLinkedList {
public:
    // 定义单链表
    struct ListNode {
        int val;
        ListNode* next;
        ListNode(int _val):val(_val), next(nullptr){}
    }*head;
    // 链表初始化，头节点为空
    MyLinkedList() {
        head = nullptr;
    }
    // 获取元素
    int get(int index) {
        // 索引无效返回-1
        if (index < 0) return -1;
        // 找到第index个点
        auto p = head;
        for (int i = 0; i < index && p; i ++) p = p->next;
        if (!p) return -1;
        return p->val;
    }
    // 在头节点前添加元素
    void addAtHead(int val) {
        auto cur = new ListNode(val);
        cur->next = head;
        head = cur;
    }
    // 在尾节点后添加元素
    void addAtTail(int val) {
        // 如果头节点不存在，新加入的元素就是头节点
        if (!head) head = new ListNode(val);
        else {
            // 找到尾节点，在后面添加元素
            auto p = head;
            while (p->next) p = p->next;
            p->next = new ListNode(val);
        }
    }
    // 在第index点前添加一个元素
    void addAtIndex(int index, int val) {
        // 如果 index<=0，相当于在头节点添加元素
        if (index <= 0) addAtHead(val);
        else {
            // 求链表总长度，如果 index 等于链表长度相当于在尾节点插入元素
            int len = 0;
            for (auto p = head; p; p = p->next) len ++;
            if (index == len) addAtTail(val);
            else if (index < len){
                // 找到第 index 点的前驱节点，将其插入
                auto p = head;
                for (int i = 0; i < index - 1; i ++) p = p->next;
                auto cur = new ListNode(val);
                cur->next = p->next;
                p->next = cur;
            }
        }
    }
    // 删除第index个节点
    void deleteAtIndex(int index) {
        int len = 0;
        for (auto p = head; p; p = p->next) len ++;
        if (index >= 0 && index < len){
            // index 等于 0 相当于删除头节点
            if (!index) head = head->next;
            else {
                auto p = head;
                for (int i = 0; i < index - 1; i ++) p = p->next;
                p->next = p->next->next;
            }
        }
    }
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

leetcode.24 两两交换链表中的节点

• 链接https://leetcode.cn/problems/swap-nodes-in-pairs/
• 解题方法：迭代
• leetcode解题代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        auto dummy = new ListNode(-1);
        dummy->next = head;

        auto a = dummy;
        while (a->next && a->next->next){
            auto b = a->next;
            auto c = a->next->next->next;

            a->next = a->next->next;
            a->next->next = b;
            a->next->next->next = c;

            a = a->next->next; 
        }
        return dummy->next;

    }
};

leetcode.237 删除链表中的节点

• 链接https://leetcode.cn/problems/delete-node-in-a-linked-list/
• 解题方法：
  本题不是常规意义上的删除节点，无法找到当前节点的前驱节点
  方法比较取巧，即先把后继节点的值赋值给当前节点，然后再删除后继节点
• leetcode解题代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val = node->next->val;
        node->next = node->next->next;
    }
};

leetcode.19 删除链表的倒数第 N 个结点

• 链接https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
• 解题方法：
  常规删除节点的方法，找到倒数第 $N$ 个结点的前驱节点，将第 $N$ 个节点删除
• leetcode解题代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // 防止头节点被删除
        auto dummy = new ListNode(-1);
        dummy->next = head;
        // 统计链表长度
        int len = 0;
        for (auto p = dummy; p; p = p->next) len ++;
        // 找到需要删除节点的前驱节点
        // 倒数第 n 个节点即正数第 len-n 个节点
        // 需要移动 len-n-1 次
        auto p = dummy;
        for (int i = 0; i < len - n - 1; i ++) p = p->next;
        // 删除节点
        p->next = p->next->next;
        return dummy->next; 
    }
};

leetcode.61 旋转链表

• 链接https://leetcode.cn/problems/rotate-list/
• 解题方法：画图
  1. 旋转 k 次，如果 k 是链表长度的倍数，相当于没有旋转
  2. 旋转 k 次，要找到倒数第 k+1 个节点，将其指向空
  3. 将倒数第 k 个节点定义为新的头节点，并将尾节点指向原来的头节点
• leetcode解题代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head) return head;
        // 旋转的次数如果是链表长度的倍数，相当于没有旋转
        int len = 0;
        for (auto p = head; p; p = p->next) len ++;
        k %= len;
        if (!k) return head;

        auto p = head;
        for (int i = 0; i < len - k - 1; i ++) p = p->next;

        auto tail = head;
        while (tail->next) tail = tail->next;

        tail->next = head;

        auto new_head = p->next;

        p->next = nullptr;
        return new_head;
    }
};

leetcode.143 重排链表

• 链接https://leetcode.cn/problems/reorder-list/
• 解题方法：
  1. 通过快慢指针将链表从中点一分为二，如果链表的长度为偶数，取前一个节点
  2. 将后半部分链表反转
  3. 将两个链表合并
• leetcode解题代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if (!head || !head->next) return;

        auto s = head, f = head;
        while (f && f->next && f->next->next){
            s = s->next;
            f = f->next->next;
        }
        auto new_head = s->next;
        s->next = nullptr;

        new_head = reverseList(new_head);
        
        while (new_head){
            auto cur = new_head->next;
            new_head->next = head->next;
            head->next = new_head;
            head = new_head->next;
            new_head = cur;
        }
    }

    ListNode* reverseList(ListNode* head){
        if (!head || !head->next) return head;

        auto a = head, b = a->next;
        while (b){
            auto c = b->next;
            b->next = a;
            a = b, b = c;
        }
        head->next = nullptr;
        return a;
    }
};

leetcode.138 复制带随机指针的链表

• 链接https://leetcode.cn/problems/copy-list-with-random-pointer/
• 解题方法：
  1. 将原链表赋值一份接到后面 1->2->3->4 => 1->1->2->2->3->3->4->4
  2. 创建新链表节点的随机指针，新链表随机指针和原链表随机指针存在关系
     p->next->random = p->random->next;
  3. 将原链表和新链表拆分
• leetcode解题代码

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) return NULL;
        // 1.将原链表每个节点复制一份接在原节点后
        // 例如：1->2->3->4  =>  1->1->2->2->3->3->4->4
        auto p = head;
        while (p){
            auto copy = new Node(p->val);
            copy->next = p->next;
            p->next = copy;
            p = copy->next;
        }
        // 2.p->next->random = p->random->next
        for (auto p = head; p; p = p->next->next){
            if (p->random)
                p->next->random = p->random->next;
        }
        // 3.将新链和原链拆分，将原链恢复原状，将新链返回
        auto cur = head->next, pre = head, res = head->next;
        while (cur->next){
            pre->next = pre->next->next;
            cur->next = cur->next->next;
            pre = pre->next;
            cur = cur->next;
        }
        pre->next = NULL;
        return res;
    }
};