关于链表的几道经典题目

前言

关于链表的基础结构本文不做过多的阐述，介绍可以参考Hello算法 。

设计链表

题目 707. 设计链表

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

• MyLinkedList() 初始化 MyLinkedList 对象。
• int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
• void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
• void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
• void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
• void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

示例：

输入
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
输出
[null, null, null, null, 2, null, 3]

解释
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3
myLinkedList.get(1);              // 返回 2
myLinkedList.deleteAtIndex(1);    // 现在，链表变为 1->3
myLinkedList.get(1);              // 返回 3

思路

这道题主要是考察链表的基础功能实现，本质上没有太多的算法上的优化思路。

class MyLinkedList {
public:
    // 定义链表节点结构体
    struct LinkedNode {
        int val;
        LinkedNode* next;
        LinkedNode(int val):val(val), next(nullptr){}
    };

    // 初始化链表
    MyLinkedList() {
        _dummyHead = new LinkedNode(0);
        _size = 0;
    }
    
    int get(int index) {
        if(index < 0 || index >= _size) return -1;
        LinkedNode* cur = _dummyHead->next;
        while(index--)
        {
            cur = cur->next;
        }
        return cur->val;
    }
    
    void addAtHead(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        newNode->next = _dummyHead->next;
        _dummyHead->next = newNode;
        _size++;
    }
    
    void addAtTail(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = _dummyHead;
        while(cur->next != nullptr)
        {
            cur = cur->next;
        } 
        cur->next = newNode;
        _size++;
    }
    
    void addAtIndex(int index, int val) {
        if(index > _size) return;
        if(index < 0) index = 0;
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = _dummyHead;
        while(index--)
        {
            cur = cur->next;
        }
        newNode->next = cur->next;
        cur->next = newNode;
        _size++;
    }
    
    void deleteAtIndex(int index) {
        if(index >= _size || index < 0) return;
        LinkedNode* cur = _dummyHead;
        while(index--)
        {
            cur = cur->next;
        }
        LinkedNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        tmp = nullptr;
        _size--;
    }

private:
    int _size;
    LinkedNode* _dummyHead;

};

/**
 * 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);
 */

移除

虚拟头节点

在上一个问题中，我们使用到了虚拟头节点dummyHead，其主要作用是作为一个辅助节点，使链表的操作更加简单和统一。。下面是虚拟头节点的一些好处总结：

1. 简化和统一处理：当需要在链表前面进行添加或删除节点时，通常需要检查是否在头部进行操作，因为头部节点前方没有别的节点，增删操作与中间的节点有所不同。有了虚拟头节点，就可以统一进行操作。
2. 避免空指针异常：如果没有虚拟头节点，在空链表上执行删除或添加操作时，需要特别注意以避免发生空指针异常。使用虚拟头节点可以保证链表始终有一个非空的节点。
3. 易于管理：在某些情况下，比如在双向链表中，虚拟头节点和虚拟尾节点可以简化节点的管理，因为你总是有一个确定的开始和结束节点。
4. 辅助节点：在某些算法中，如快慢指针寻找链表中点或环的起点时，虚拟头节点可以作为一个辅助节点，便于算法的实现和理解。

移除元素

移除元素是链表最基础的操作之一，其方法可以叙述三步为：断链，跨越重连、删除。第一步顾名思义，断开原有链接，第二步跨越原来的节点，连接到下一个节点。第三步是c/c++特有的，因为没有回收机制，所以需要手动删除。

那么针对203. 移除链表元素，删除算法可以写为：

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* cur = dummyHead;
        while(cur->next!=nullptr)
        {
            if(cur->next->val == val)
            {
                ListNode* temp = cur->next;
                cur->next = temp->next;
                delete temp;
            }
            else
            {
                cur = cur->next;
            }
        }
        head = dummyHead->next;
        delete dummyHead;
        return head;
    }
};

删除链表倒数第N的元素

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

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

img

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

对于这道题，最容易想到的是：第一次遍历算出总节点数，再计算倒数第n个是正数第i个，再遍历到第i个并返回。除此之外我们其实可以想到在数组一章中讲到的双指针的思路。即，快指针在慢指针前面n个，当快指针到达末尾，慢指针位置就是倒数第n个。虽然双指针看似也是遍历两遍，但两者本质区别在于，第二种方法操作起来更加统一简单。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* slow = dummyHead;
        ListNode* fast = dummyHead;
        while(n-- && fast != nullptr)
        {
            fast = fast->next;
        }
        while(fast->next != nullptr)
        {
            fast = fast->next;
            slow = slow->next;
        }
        ListNode* tmp = slow->next;
        slow->next = tmp->next;
        delete tmp;
        return dummyHead->next;

    }
};

反转

交换（两两交换链表中的节点）

链表相交

环形链表