链表

1. 链表简介

链表的类型

单链表：有指向下一个结点的指针

双链表：有指向前结点和后结点的指针

循环链表：尾结点指向头结点，形成环

链表的存储方式

是不连续的，散乱分布在内存中的地址上

链表的定义

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

通过自己定义构造函数初始化节点：

ListNode* head = new ListNode(5);

使用默认构造函数初始化节点：

ListNode* head = new ListNode();
head->val = 5;

链表的操作

删除节点

添加结点

2. 移除链表元素

203. 移除链表元素【简单】

相同题目：剑指 Offer 18. 删除链表的节点

题目意思：删除所有满足node.val==val的结点

方法一：迭代

时间复杂度：O(n) n为链表长度；遍历链表一次

空间复杂度：O(1)

class Solution {
public:
    //迭代
    ListNode* removeElements(ListNode* head, int val) {
        auto dummyHead = new ListNode(0, head);  //生成一个虚拟头结点，结点值为0，next指向head
        auto node = dummyHead;       //这个结点现在是head结点的前一个结点
        while (node->next != NULL) {            //遍历后面的结点
            if (node->next->val == val) {
                node->next = node->next->next;  //修改指针指向
            }
            else {
                node = node->next;
            }
        }
        return dummyHead->next;
    }
};

注意：使用C++来做leetcode，如果移除一个节点之后，没有手动在内存中删除这个节点，leetcode依然也是可以通过的，只不过，内存使用的空间大一些而已，但建议依然要养成手动清理内存的习惯。

手动管理内存如下：

class Solution {
public:
    //迭代
    ListNode* removeElements(ListNode* head, int val) {
        auto dummyHead = new ListNode(0, head);  //生成一个虚拟头结点，结点值为0，next指向head
        auto node = dummyHead;       //这个结点现在是head结点的前一个结点
        while (node->next != NULL) {            //遍历后面的结点
            if (node->next->val == val) {
                auto temp = node->next;
                node->next = node->next->next;  //修改指针指向
                delete temp;
            }
            else {
                node = node->next;
            }
        }
        auto res = dummyHead->next;
        delete dummyHead;
        return res;
    }
};

思路二：递归

时间复杂度：O(n)

空间复杂度：O(n)

class Solution {
public:
    //递归
    ListNode* removeElements(ListNode* head, int val) {
        if (head == nullptr) return head;                   //判断是否为空链表
        head->next = removeElements(head->next, val);  //从第二个元素开始递归
        return head->val == val ? head->next : head;   //判断头结点是否等于val
    }
};

3. 设计链表

707. 设计链表【中等】

class MyLinkedList {
private:
    // 定义链表节点结构体
    struct LinkedNode {
        int val;
        LinkedNode* next;
        LinkedNode(int val) :val(val), next(nullptr) {}
    };
    int _size;
    LinkedNode* _dummyHead;
public:
    // 初始化链表
    MyLinkedList() {
        _dummyHead = new LinkedNode(0); // 这里定义的头结点 是一个虚拟头结点，而不是真正的链表头结点
        _size = 0;
    }
    // 1. 获取指定index的val值
    int get(int index) {
        if (index > (_size - 1) || index < 0)    return -1; //索引越界返回-1，
        LinkedNode* cur = _dummyHead;
        for (int i = 0; i <= index; i++) {
            cur = cur->next;
        }
        return cur->val;
    }
    // 2. 头插结点
    void addAtHead(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        newNode->next = _dummyHead->next;
        _dummyHead->next = newNode;
        _size++;
    }
    // 3. 尾插结点
    void addAtTail(int val) {
        LinkedNode* cur = _dummyHead;
        while (cur->next != nullptr) {              //先移动到最后一个结点
            cur = cur->next;
        }
        LinkedNode* newNode = new LinkedNode(val);  //再插入节点
        cur->next = newNode;
        _size++;
    }
    // 4. 指定index插入节点
    void addAtIndex(int index, int val) {
        if (index > _size)   return;
        LinkedNode* cur = _dummyHead;
        for (int i = 0; i < index; i++) {            //移动到插入位置的前面结点
            cur = cur->next;
        }
        LinkedNode* newNode = new LinkedNode(val);   //插入节点，头插方法包含在内
        newNode->next = cur->next;
        cur->next = newNode;
        _size++;
    }
    // 5. 删除指定index的结点
    void deleteAtIndex(int index) {
        if (index >= _size || index < 0)    return;
        LinkedNode* cur = _dummyHead;
        for (int i = 0; i < index; i++) {   //移动到需要删除位置的前面结点
            cur = cur->next;
        }
        LinkedNode* tmp = cur->next;        //删除节点
        cur->next = cur->next->next;
        delete tmp;
        _size--;
    }
};

4. 翻转链表

206. 反转链表【简单】

思路一：栈

倒序反转的最适合栈；可以存储val值，也可以存储结点；然后重新生成一条链表。

思路二：使用双指针修改指向

时间复杂度：O(n)

空间复杂度：O(1)

class Solution {
public:
    //双指针实现修改指向  下一个指向前一个
    ListNode* reverseList(ListNode* head) {
        ListNode* fast = head;        //快指针指向头结点  慢指针指向头结点的前一个结点，即NULL
        ListNode* slow = NULL;
        while (fast != nullptr) {
            ListNode* next = fast->next;
            fast->next = slow;      //核心代码，修改指向
            slow = fast;            //前移两个指针
            fast = next;
        }
        return slow;
    }
};

思路三：递归套娃

时间复杂度：O(n)

空间复杂度：O(n)；取决于递归调用的栈空间

class Solution {
public:
    ListNode* reverse(ListNode* pre,ListNode* cur){
        if(cur == NULL) return pre;
        ListNode* temp = cur->next;
        cur->next = pre;
        // 可以和双指针法的代码进行对比，如下递归的写法，其实就是做了这两步
        // pre = cur;
        // cur = temp;
        return reverse(cur,temp);
    }
    ListNode* reverseList(ListNode* head) {
        // 和双指针法初始化是一样的逻辑
        // ListNode* cur = head;
        // ListNode* pre = NULL;
        return reverse(NULL, head);
    }
};

5. 两两交换链表中的结点

24. 两两交换链表中的节点【中等】

方法一：暴力破解

class Solution {
public:
  //暴力法
  //两个容器，一个存奇数索引的val，一个存偶数索引的val，  生成一条新的链表
  ListNode* swapPairs(ListNode* head) {
    vector<int> v1, v2;
    auto node = head;
    int num = 1;
    while (node != nullptr) {                        //1.容器存val值
      if (num % 2 == 1) v1.push_back(node->val);
      else v2.push_back(node->val);
      node = node->next;
      num++;
    }
    auto preHead = new ListNode(0);
    auto temp = preHead;
    for (int i = 0; i < v2.size(); i++) {             //2.生成新链表
      temp->next = new ListNode(v2[i]);
      temp = temp->next;
      temp->next = new ListNode(v1[i]);
      temp = temp->next;
    }
    if (v1.size() > v2.size()) {                      //链表长度为奇数的情况
      temp->next = new ListNode(v1.back());
    }
    return preHead->next;
  }
};

方法二：双指针

class Solution {
public:
  ListNode* swapPairs(ListNode* head) {
    ListNode* dummyHead = new ListNode(0, head); // 设置一个虚拟头结点
    ListNode* cur = dummyHead;
    while (cur->next != nullptr && cur->next->next != nullptr) {
      ListNode* tmp = cur->next;                  // 记录临时节点
      ListNode* tmp1 = cur->next->next->next;     // 记录临时节点
      cur->next = cur->next->next;    // 步骤一
      cur->next->next = tmp;          // 步骤二
      cur->next->next->next = tmp1;   // 步骤三
      cur = cur->next->next;          // cur移动两位，准备下一轮交换
    }
    return dummyHead->next;
  }
};

6. 删除链表的倒数第N个节点

19.删除链表的倒数第N个节点【简单】

思路一：使用vector容器存结点，索引找到待删除节点的前一个结点，修改指向

思路二：使用栈的压入和弹出，翻转就要想到栈

思路三：两次遍历，第一次遍历计数，第二次遍历实现删除

思路四：双指针

思路二：快慢双指针；使得两指针维持一定间隔，当快指针指向空结点时，慢指针指向需要删除的结点的前一个结点

class Solution {
public:
  ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* start = new ListNode(0, head);  //1.head前面生成一个结点
    ListNode* fast = head;
    ListNode* slow = start;
    for (int i = 0; i < n; ++i) {  //2.移动快指针   使得 fast-slow 中间隔了n个结点
      fast = fast->next;
    }
    while (fast) {           //3.快速移动fast指向最后
      fast = fast->next;
      slow = slow->next;
    }   //fast指向null时  slow结点是需要删除结点的前一个结点 
    slow->next = slow->next->next;  //4.删除节点
    ListNode* res = start->next;
    delete start;
    return res;
  }
};

7. 链表相交

160. 相交链表【简单】

相同题目：剑指 Offer 52. 两个链表的第一个公共节点

相同题目：面试题 02.07. 链表相交

思路一：双栈

自己实现了这个

思路：两条链表后面的结点肯定是相同的，我们倒序找到最后一个相同的结点。

实现倒序就要用到栈

class Solution {
public:
  //双栈
  //时间复杂度：O(m+n)    遍历两链表
  //空间复杂度：O(m+n)    存入两链表
  ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
    stack<ListNode*> sA;
    stack<ListNode*> sB;
    if (headA == nullptr || headB == nullptr) return NULL;   //排除特殊情况
    auto nodeA = headA;                 //1.两条链表入两个栈
    while (nodeA != nullptr) {
      sA.push(nodeA);
      nodeA = nodeA->next;
    }
    auto nodeB = headB;
    while (nodeB != nullptr) {
      sB.push(nodeB);
      nodeB = nodeB->next;
    }
    if (sA.top() != sB.top()) return NULL;   //两链表最后一个数都不相同  就没有交集
    int sizeMin = min(sA.size(), sB.size());
    while (sizeMin != 0) {
      if (sA.top() == sB.top()) {
        sA.pop();
        sB.pop();
      }
      else {
        return sA.top()->next;     //2.找到交集的起始结点
      }
      sizeMin--;
    }
    return sA.size() > sB.size() ? headB : headA;   //while循环没else语句跳出  则其中短的链表就是交集   所以返回它的起始结点
  }
};

思路二：哈希表存链表A的结点；然后遍历查找链表B的结点

class Solution {
public:
  //哈希表也能实现功能
  //时间复杂度：O(m+n)   mn分别为两链表的长度  因为需要遍历两链表
  //空间复杂度：O(m)     一链表的长度
  ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
    unordered_set<ListNode*> set;
    ListNode* nodeA = headA;     //1.先把链表A的结点全部存入
    while (nodeA) {
      set.insert(nodeA);
      nodeA = nodeA->next;
    }
    auto nodeB = headB;
    while (nodeB) {
      if (set.count(nodeB))   return nodeB;//2.在哈希表中查找链表B的结点  查到则返回
      nodeB = nodeB->next;
    }
    return NULL;   //3.没查到，说明没有交集
  }
};

思路三：双指针，浪漫的相遇

具体思路看此人的动图演示：链接

空间复杂度：O(1)

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *node1 = headA;
        ListNode *node2 = headB;
        while (node1 != node2) {
            node1 = node1 != NULL ? node1->next : headB;
            node2 = node2 != NULL ? node2->next : headA;
        }
        return node1;
    }
};

思路四：对齐链表右边，再遍历

时间复杂度：O(1)

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* curA = headA;
        ListNode* curB = headB;
        int lenA = 0, lenB = 0;
        while (curA != NULL) {   // 求链表A的长度
            lenA++;
            curA = curA->next;
        }
        while (curB != NULL) {    // 求链表B的长度
            lenB++;
            curB = curB->next;
        }
        curA = headA;
        curB = headB;
        // 让curA为最长链表的头，lenA为其长度
        if (lenB > lenA) {
            swap (lenA, lenB);
            swap (curA, curB);
        }
        // 求长度差
        int gap = lenA - lenB;
        // 让curA和curB在同一起点上（末尾位置对齐）
        for(int i = 0; i < gap; i++){
            curA = curA->next;
        }
        // 遍历curA 和 curB，遇到相同则直接返回
        while (curA != NULL) {
            if (curA == curB)   return curA;
            curA = curA->next;
            curB = curB->next;
        }
        return NULL;
    }
};

8. 环形链表

141. 环形链表【简单，哈希表，双指针】

升级版本题目：142. 环形链表 II

题目意思：给你链表判断是否有环

思路一：哈希表

class Solution {
public:
  //哈希表
  //时间复杂度：O(n)  
  //空间复杂度：O(n)   多余容器空间
  bool hasCycle(ListNode* head) {
    unordered_set<ListNode*> res;
    while (head != nullptr) {    //1.哈希表存结点，判断当前需要存储的结点，哈希表中是否存在；存在则有环
      if (res.count(head)) {
        return true;
      }
      res.insert(head);       
      head = head->next;     //实现结点的移动
    }
    return false;
  }
};

思路二：双指针

class Solution {
public:
  //一快一慢双指针  
  //时间复杂度：O(N)  一个while循环
  //空间复杂度：O(1)  两个指针空间 
  bool hasCycle(ListNode* head) {
    if(head==nullptr || head->next==nullptr)  return false;    //排除0,1结点情况
    ListNode* slow = head;
    ListNode* fast = head->next;
    while (fast->next != nullptr) {   //两相邻指针，  若fast指针跑到slow后面去了  则有环
      fast = fast->next;
      slow = slow->next;
      if (slow >= fast) {   //为啥这句能成功？
        return true;
      }
    }
    return false;
  }
};

快指针走两步，慢指针走一步

正版双指针思路：https://leetcode-cn.com/problems/linked-list-cycle/solution/dai-ma-sui-xiang-lu-141-huan-xing-lian-b-h1jq/

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head==nullptr || head->next==nullptr)  return false;    //排除0,1结点情况
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast != NULL && fast->next != NULL) {
            slow = slow->next;               //慢指针走一步  快指针走两步  相遇证明有环
            fast = fast->next->next;
            if (slow == fast) return true;   // 快慢指针相遇，说明有环
        }
        return false;                       //能走到NULL说明就没环
    }
};

142. 环形链表 II【中等】

思路一：哈希表

与上一题相比，只是修改了返回值

class Solution {
public:
  ListNode* detectCycle(ListNode* head) {
    unordered_set<ListNode*> set;    //值存结点对应的索引
    auto node = head;
    while (node != nullptr) {
      if (set.count(node))   return node;
            set.insert(node);
      node = node->next;
    }
    return NULL;
  }
};

思路二：双指针，相邻指针

//2.双指针
class Solution {
public:
  ListNode* detectCycle(ListNode* head) {
    if (head == nullptr || head->next == nullptr) return NULL;
    auto slow = head;
    auto fast = head->next;
    while (fast != nullptr) {
      slow = slow->next;
      fast = fast->next;
      if (slow >= fast) {   //等于号不能少  少了超时
        return fast;
      }
    }
    return NULL;
  }
};

思路三：快慢指针，慢的走一步，快的走两步

就是这个难，可以结合官方讲解和代码随想录的一起学习

class Solution {
public:
  ListNode* detectCycle(ListNode* head) {
    ListNode* fast = head;
    ListNode* slow = head;
    while (fast != NULL && fast->next != NULL) {
      slow = slow->next;
      fast = fast->next->next;
      // 快慢指针相遇，此时从head 和 相遇点，同时查找直至相遇
      if (slow == fast) {    //有环，寻找环的入口
        ListNode* index1 = fast;
        ListNode* index2 = head;
        while (index1 != index2) {
          index1 = index1->next;
          index2 = index2->next;
        }
        return index2;    // 返回环的入口
      }
    }
    return NULL;   //无环遍历到底端
  }
};

思路三：快慢指针，慢的走一步，快的走两步
就是这个难，可以结合官方讲解和[代码随想录](https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/142-huan-xing-lian-biao-ii-jian-hua-gong-shi-jia-2/)的一起学习
[外链图片转存中...(img-TMOVWBNw-1639994897563)]
```c++
class Solution {
public:
  ListNode* detectCycle(ListNode* head) {
    ListNode* fast = head;
    ListNode* slow = head;
    while (fast != NULL && fast->next != NULL) {
      slow = slow->next;
      fast = fast->next->next;
      // 快慢指针相遇，此时从head 和 相遇点，同时查找直至相遇
      if (slow == fast) {    //有环，寻找环的入口
        ListNode* index1 = fast;
        ListNode* index2 = head;
        while (index1 != index2) {
          index1 = index1->next;
          index2 = index2->next;
        }
        return index2;    // 返回环的入口
      }
    }
    return NULL;   //无环遍历到底端
  }
};

【代码随想录】第4章：链表

链表

1. 链表简介

链表的类型

链表的存储方式

链表的定义

链表的操作

2. 移除链表元素

203. 移除链表元素【简单】

3. 设计链表

707. 设计链表【中等】

4. 翻转链表

206. 反转链表【简单】

5. 两两交换链表中的结点

24. 两两交换链表中的节点【中等】

6. 删除链表的倒数第N个节点

19.删除链表的倒数第N个节点【简单】

7. 链表相交

160. 相交链表【简单】

8. 环形链表

141. 环形链表【简单，哈希表，双指针】

142. 环形链表 II【中等】

热门文章

最新文章

相关电子书

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

【代码随想录】第4章：链表

链表

1. 链表简介

链表的类型

链表的存储方式

链表的定义

链表的操作

2. 移除链表元素

203. 移除链表元素【简单】

3. 设计链表

707. 设计链表【中等】

4. 翻转链表

206. 反转链表【简单】

5. 两两交换链表中的结点

24. 两两交换链表中的节点【中等】

6. 删除链表的倒数第N个节点

19.删除链表的倒数第N个节点【简单】

7. 链表相交

160. 相交链表【简单】

8. 环形链表

141. 环形链表【简单，哈希表，双指针】

142. 环形链表 II【中等】

热门文章

最新文章

相关电子书